Где найти алгоритмы для стандартных математических функций?
Я надеюсь отправлять патч к библиотеке стандарта языка программирования D, которая позволит большой части std.math быть оцененной во время компиляции с помощью средств оценки функции времени компиляции языка. Оценка функции времени компиляции имеет несколько ограничений, самое важное быть:
- Вы не можете использовать ассемблер.
- Вы не можете назвать код C или кодировать, которому источник в других отношениях недоступен.
Несколько функций std.math нарушают версии этого и времени компиляции, должен быть записан. Где я могу получить информацию о хороших алгоритмах для вычислительных вещей, таких как логарифмы, экспоненты, полномочия и аккуратные функции? Я предпочитаю просто описания высокого уровня алгоритмов к фактическому коду по двум причинам:
Для предотвращения легальной неоднозначности и потребности заставить мой код выглядеть "достаточно отличающимся" от источника для проверки, я владею авторским правом.
Я хочу простые, портативные алгоритмы. Я не забочусь о микрооптимизации, пока они по крайней мере асимптотически эффективны.
Править: Модель оценки функции времени компиляции D позволяет результатам с плавающей точкой, вычисленным во время компиляции отличаться от вычисленных во времени выполнения во всяком случае, таким образом, я не забочусь, не дают ли мои алгоритмы времени компиляции точно тот же результат как версию среды выполнения, пока они не меньше с точностью до практически значительной степени.
8 ответов
John Hart Компьютерные аппроксимации 1968 г. Джон Уили и Сыновья.
Расчеты в идеале должны точно соответствовать тому, что, если они сделаны во время выполнения. Это может быть сложно. Для многих функций серия быстро не сходится на полную область, поэтому Algoritms вставляют вместе различные методы.
Кроме того, есть различные форматы плавающих точек. Большинство платформ (я думаю) теперь используйте IEEE 754. Когда я написал компилятор CA. 1985 год мне пришлось разобраться с форматами с плавающей платформой. Это было очень утомительно, чтобы получить его правильно, потому что вы должны быть битыми кусочками числа, будучи уверенным, что вы получаете именно значение, которое будет рассчитано на целевой машине. Я не знаю, если вы должны иметь дело с этим.
Есть незаконченное приложение :: WX :: Podeditor на CPAN.
-121--3171163-Источником, который я рекомендую, является Численные методы для ученых и инженеров R. Hamming.
Эта книга публикуется Press Dover и является недорогой мягкойбой.
Книга Жан-Мишель Мюллера - отличная рекомендация, как и Харт.
На самом деле это необходимо для вас владеть авторским правом? Обычно это плохое представление о том, чтобы вступить в бизнес писать функции по математике, если вы можете избежать этого (и я говорю, что, как тот, кто делает это профессионально). Я не знаю, могут ли D можно взять в BSD-лицензированном коде, но есть несколько хороших реализаций с открытым исходным кодом, которые могут оказаться полезными. Вы можете посмотреть на Sun's Fdlibm , например. Стивен Моширский Chephes также будет возможность, хотя его лицензионная ситуация немного странная, но я считаю, что он готов позволить людям перераспределить его код по другим лицензиям в прошлом.
На стороне, если вы не поддерживаете произвольную точность с плавающей точкой (я не думаю, что D), обычно не является понятия «асимптотической эффективности» для функций SIBM.
Как вы ожидаете, подобные проблемы возникают на других языках:
http://java.sun.com/j2se/1.5.0/docs/api/java/lang/strictmath.html
Чтобы помочь обеспечить переносимость Java Программы, определения некоторых из Числовые функции в этом пакете требовать, чтобы они давали то же самое результаты как определенные опубликованные алгоритмы. Эти алгоритмы Доступно из известной сети Библиотека Netlib как пакет "свободно Распространяемая математическая библиотека «FDLIBM. Эти алгоритмы, которые написаны в Язык программирования C, тогда быть понятым, как выполнено со всеми операции с плавающей точкой после Правила с плавающей точкой Java арифметика.
Я не знаю, какие правила D'S предназначены для расчета времени выполнения математических функций, но вы сможете потянуть аналогичный трюк - повторный интерпретацию C источника C FDLIBM в виде D. Если D звонит на платформенные библиотеки C, Тогда у вас возникла проблема, что может быть невозможно во время компиляции, чтобы предсказать значение выполнения.
Я думаю, что лицензия FDLIBM очень разрешена, вам придется проверить для себя, подходит ли она для перераспределения в D. Одна версия, которую я видел, требует сохранения уведомления об авторских правах, и это.
См. Книга «Элементарные функции: алгоритмы и реализация» Жан-Мишель Мюллер.
Может быть, это поможет вам (по крайней мере, для некоторых функций): http://en.wikipedia.org/wiki/cordic
См. Автономный код для численных вычислений для связи с кодом для нескольких специальных функций и для генерации случайных чисел. Весь код там является общественным достоянием. Код реализован на языках Си++ и Python, но легко транслируется на любой другой язык.
несколько источников, в том числе:
Абрамовиц и Стегун, "Руководство по математическим функциям" (доступно online!)
Харт, "Компьютерные подходы" (не напечатано, но хорошо)
также см. ряд других SO вопросов по тригонометрии, в том числе "Как работают тригонометрические функции?" и "Тригонометрические функции во встраиваемых системах".