В чем сложность функции журнала?

Ответ 1

Это действительно зависит от того, какие значения вы хотите вычислить логарифмом.

Для удваивания IEEE многие процессоры могут принимать логарифмы в одной команде сборки; Например, x86 имеет инструкции FYL2X и FYL2XP1. Хотя типичные инструкции, подобные этим, будут брать только логарифм в некоторой фиксированной базе, их можно использовать для выполнения логарифмов в произвольных базах, используя тот факт, что

log _a b = log _c b/log _c a

просто беря два логарифма и находим их частное.

Для общих целых чисел (произвольной точности) вы можете использовать повторное квадратирование в сочетании с бинарным поиском для выполнения логарифмов, используя только арифметические операции O (log log n) (каждый раз, когда вы набираете число, вы удваиваете показатель, что означает, что вы может только квадратный номер журнала журнала n раз, прежде чем вы превысите его значение и можете выполнить двоичный поиск). Используя некоторые симпатичные трюки с номерами Фибоначчи, вы можете сделать это только в пространстве O (log n). Если вы вычисляете двоичный логарифм есть несколько милых трюков, которые вы можете использовать с битовыми сдвигами, чтобы вычислить значение за меньшее время (хотя асимптотика сложность такая же).

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

Надеюсь, это поможет!