Вопрос по algorithm, math – Как программируются логарифмы? [закрыто]

7

Они просто выяснили, используя подход грубой силы, или есть алгоритм для этого?

«грубая сила»; является свойством алгоритмов, где вы применяете больше вычислительной мощности, чтобы избавиться от лишних раздумий (которые вы могли бы использовать, чтобы найти менее грубый алгоритм). starblue
«грубая сила»; и «алгоритм»; не являются взаимоисключающими, ваш вопрос создает ложную дихотомию. И ответ - ДА, в этом есть алгоритм. High Performance Mark
Ах, я чувствую себя глупо, забыв, что грубая сила была на самом деле алгоритмом. Благодарю. Taffer

Ваш Ответ

2   ответа
2

Есть несколько способов вычисления логарифмов. Увидетьэтот.

-1. Они не "в основном рассчитываются по приближениям ряда Тейлора".
Я обновил ответ, чтобы больше этого не говорить.
15

Реализация такой функции, как натуральный логарифм в любой приличной математической библиотеке, будет держать ошибку ниже ulp (единицы наименьшей точности). Цель разработчика математической библиотечной функции - найти оптимальное приближение, которое достигает желаемой точности при минимальном количестве вычислений. Ряды Тейлора, как правило, плохой выбор, потому что для достижения желаемой точности требуется слишком много терминов.

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

В случае натурального логарифма есть простой способ уменьшить диапазон. Вещественные числа почти повсеместно представлены в терминах мантиссы и показателя степени:x=m*2p, гдеp является целым числом иm находится между 1 и 2. Таким образом, log (x) = log (m)+p* Журнал (2). Последний термин,p* log (2), это просто умножение на известную константу. Таким образом, проблема сводится к нахождению логарифма числа от 1 до 2 (или от 1/2 до 1). Дальнейшее уменьшение диапазона может быть сделано с использованием факта, что & # x221A; 2 находится логарифмически в середине [1,2). Таким образом, все, что нужно, - это способ вычисления логарифма числа между 1 и & # x221A; 2. Обычно это делается с помощью рационального полинома. Отношение многочлена второго порядка к третьему порядку вполне подходит для этого.

Уменьшение диапазона до [1.0, 2.0) приводит к большим ошибкам вблизи log (0.999 ...), как прокомментировал Дэвид Хаммен. Реализации, о которых я знаю, позволяют избежать этой проблемы, сократив диапазон до 1,0 во внутренней части, например, [2/3, 4/3) или [sqrt (0.5), sqrt (2.0)). В терминах программирования это всего лишь несколько дополнительных инструкций, чтобы сделать это: if (m & gt; constant) {p + = 1; м * = 0,5;}
Хороший комментарий 0,5 ULP слишком амбициозны. Относительно рациональных многочленов по сравнению с простыми: рациональные могут быть лучше, если сокращение степени больше, чем компенсирует увеличение стоимости деления против умножения. Я нашел несколько реализацийlog которые используют рациональный многочлен. Журнал очень хорошая функция, насколько приближение. Наихудшие ошибки происходят с числами, близкими к единице, и даже здесь ошибка может быть сохранена с точностью до ULP.
.5 ULP - амбициозная цель; это то же самое, что и правильно округленное, означающее, что должно быть возвращено представимое число, ближайшее к математически точному результату. Проект CRlibm (lipforge.ens-lyon.fr/www/crlibm) стремится сделать это, но оно неполное (например, обратные гиперболические функции не предусмотрены). Верное округление (менее 1 ULP) является более достижимой целью, и типичные библиотеки допускают ошибки нескольких ULP. Рациональных функций избегают, поскольку на обычных процессорах деление происходит медленно. Например, касательная может использовать рациональную функцию, но синус и логарифм будут использовать простые полиномы.

Похожие вопросы