Где найти алгоритмы для стандартных математических функций?

Question

Я собираюсь отправить патч в стандартную библиотеку языка программирования D, который позволит оценивать большую часть std.math во время компиляции с использованием средств оценки функций во время компиляции языка. Оценка функции времени компиляции имеет несколько ограничений, наиболее важными из которых являются:

1. Нельзя использовать язык ассемблера.
2. Вы не можете вызвать код C или код, для которого источник недоступен.

Несколько функций std.math нарушают их, и необходимо писать версии во время компиляции. Где я могу получить информацию о хороших алгоритмах для вычисления таких вещей, как логарифмы, показатели, степени и триггерные функции? Я предпочитаю только высокоуровневые описания алгоритмов реальному коду по двум причинам:

1. Чтобы избежать юридической двусмысленности и необходимости заставить мой код выглядеть "достаточно отличным" от исходного кода, чтобы убедиться, что я владею авторским правом.

2. Я хочу простые переносимые алгоритмы. Меня не волнует микрооптимизация, если она хотя бы асимптотически эффективна.

Редактировать: Модель оценки функции времени компиляции D позволяет результатам с плавающей запятой, вычисленным во время компиляции, так или иначе отличаться от вычисленных во время выполнения, поэтому мне все равно, если мои алгоритмы времени компиляции не дают точно тот же результат, что и во время исполнения, если они не менее точны в значительной степени.

Answer 1

Джон Харт Компьютерные аппроксимации 1968 от Джона Уайли и сыновья.

Расчеты в идеале должны точно соответствовать тому, что они делали бы, если бы выполнялись во время выполнения. Это может быть сложно. Для многих функций никакие серии не сходятся быстро по всей области, поэтому алгоритмы объединяют различные методы.

Кроме того, существуют различные форматы с плавающей запятой. Большинство платформ (я думаю) сейчас используют IEEE 754. Когда я написал компилятор ок. В 1985 году мне пришлось иметь дело с кроссплатформенными форматами с плавающей запятой. Это было очень утомительно, чтобы понять это правильно, потому что вы должны собирать числа по крупицам, будучи уверенными, что вы получите именно то значение, которое будет рассчитано на целевой машине. Я не знаю, придется ли вам с этим сталкиваться.

Answer 2

Книга Жана-Мишеля Мюллера - отличная рекомендация, как и Харт.

Действительно ли вам необходимо владеть авторским правом? Обычно плохая идея начать писать математические библиотечные функции, если вы можете избежать этого (и я говорю это как тот, кто делает это профессионально). Я не знаю, может ли D взять код, лицензированный BSD, но есть несколько хороших реализаций с открытым исходным кодом, которые могут оказаться полезными. Вы можете посмотреть на FDLIBM Sun, например. Cephes Стефана Мошиера также была бы возможной, хотя ее ситуация с лицензированием немного странная, но я считаю, что в прошлом он был готов позволить людям распространять его код под другими лицензиями.

В дополнение к этому, если вы не поддерживаете плавающую точку произвольной точности (я не думаю, что D поддерживает), обычно нет понятия "асимптотической эффективности" для функций libm.

Answer 3

Как и следовало ожидать, подобные проблемы возникают на других языках:

http://java.sun.com/j2se/1.5.0/docs/api/java/lang/StrictMath.html

Чтобы помочь обеспечить переносимость Java программы, определения некоторых из числовые функции в этом пакете требуют, чтобы они производили то же самое опубликованные результаты алгоритмы. Эти алгоритмы доступны из известной сети библиотека netlib как пакет "Свободно" Распространяемая математическая библиотека "fdlibm. Эти алгоритмы, которые написаны в язык программирования C, то быть понятым как исполненный со всеми операции с плавающей точкой после правила Java с плавающей точкой арифметика.

Я не знаю, каковы правила D для вычисления математических функций во время выполнения, но вы можете использовать аналогичный прием - заново интерпретировать источник C для fdlibm как D. Если D вызывает специфичные для платформы библиотеки C, тогда возникает проблема, заключающаяся в том, что во время компиляции невозможно предсказать значение времени выполнения.

Я думаю, что лицензия fdlibm очень разрешительна, вам придется самостоятельно проверить, подходит ли она для распространения в D. Одна версия, которую я видел, требует сохранения уведомления об авторских правах, и все.

Answer 4

Источник, который я рекомендую, - Численные методы для ученых и инженеров Р. У. Хэмминга.

Эта книга издана Dover Press и является недорогой книгой в мягкой обложке.

Answer 5

См. Книгу "Элементарные функции: алгоритмы и реализация" Жан-Мишель Мюллер.

Answer 6

несколько источников, в том числе:

Абрамовиц и Стегун, «Справочник по математическим функциям» (доступно онлайн !)

Харт, "Компьютерные аппроксимации" (из печати, но хорошо)

также см. Несколько других вопросов SO по тригонометрии, включая « Как работают тригонометрические функции? » и « Тригонометрические функции во встроенных системах ».

Answer 7

Может быть, это поможет вам (по крайней мере, для некоторых функций): http://en.wikipedia.org/wiki/CORDIC

Answer 8

См. Автономный код для числовых вычислений для ссылок на код для нескольких специальных функций и для генерации случайных чисел. Весь код там является общественным достоянием. Код реализован на C ++ и Python, но его легко перевести на любой другой язык.