Существует множество различных алгоритмов для вычисления логарифмов, каждый из которых представляет собой своего рода компромисс. В этом ответе рассматриваются различные подходы и некоторые связанные с этим компромиссы.
Подход 1: повторное умножение
Один простой подход для вычисления ⌊log b n⌋ - это вычисление последовательность b 0 , b 1 , b 2 , et c. пока мы не найдем значение больше, чем п. В этот момент мы можем остановиться и вернуть показатель степени непосредственно перед этим. Код для этого довольно прост:
x = 0; # Exponent
bX = 1; # b^Exponent
while (bx <= n) {
x++;
bX *= b;
}
return x - 1;
Как быстро это? Обратите внимание, что внутренний l oop считает до x = 0, x = 1, x = 2 и т. Д. c. пока в конце концов мы не достигнем x = ⌊log b x⌋, выполняя одно умножение на одну итерацию. Если мы предположим, что все целые числа, с которыми мы имеем дело, вписываются в отдельные машинные слова - скажем, мы работаем с int или long или чем-то в этом роде - тогда каждое умножение занимает время O (1), и общее время выполнения равно O (log b n) с использованием памяти O (1).
Подход 2: Повторное возведение в квадрат
Есть старый вопрос для интервью, который звучит примерно так: , У меня есть номер n, и я не собираюсь рассказывать вам, что это такое. Вы можете делать запросы в форме «x равен n, меньше n или больше n?», И ваша цель - использовать наименьшее количество запросов, чтобы выяснить, что такое n. Предполагая, что вы буквально понятия не имеете, что может быть n, один разумный подход работает так: угадать значения 1, 2, 4, 8, 16, 32, ..., 2 k , ..., пока ты не промахнешься. В этот момент используйте бинарный поиск по диапазону, который вы только что нашли, чтобы узнать, что такое n. Это выполняется за время O (log n), так как после вычисления 2 1 + log 2 n = 2n вы перескочите n, и после этого вы будете выполнять двоичный поиск в диапазоне размером n для общего времени выполнения O (log n).
Поиск логарифмов, в некотором смысле, своего рода, соответствует этой проблеме. У нас есть число n, записанное как b x для некоторого неизвестного x, и мы хотим найти x. Используя вышеуказанную стратегию в качестве отправной точки, мы можем поэтому вычислить b 2 0 , b 2 1 , b 2 2 и др. c. пока мы не промахнемся b x . Оттуда мы можем запустить вторичный двоичный поиск, чтобы выяснить точный требуемый показатель степени.
Мы можем вычислить последовательность значений b 2 k , используя факт что
b 2 k + 1 = b 2 · 2 k = (b 2 k ) 2
и найдите значение, которое выходит за пределы следующим образом:
x = 1; # exponent
bX = b; # b^x
while (bX <= n) {
bX *= bX; # bX = bX^2
x *= 2;
}
# Overshot, now do the binary search
Проблема заключается в как сделать этот бинарный поиск, чтобы понять вещи. В частности, мы знаем, что b 2 x слишком велико, но мы не знаем, насколько. И в отличие от игры «угадай число», бинарный поиск по показателю немного сложнее.
Одно милое решение этой проблемы основано на идее, что если х - это значение, которое мы Ищите, тогда мы можем записать x как последовательность битов в двоичном виде. Например, давайте напишем x = a m-1 2 m-1 + a m-2 2 m-2 +. .. + a 1 2 1 + a 0 2 0 . Тогда
б х = б а м-1 2 м-1 + а м- 2 2 м-2 + ... + a 1 2 1 + a 0 2 0
= 2 a м-1 2 м-1 · 2 a м- 2 2 м-2 · ... · 2 a 0 2 0
Другими словами, мы можем попытаться выяснить, что такое b x , накапливая x по одному биту за раз. Для этого при вычислении вычисляем значения b 1 , b 2 , b 4 , b 8 и др. c. мы можем записать значения, которые мы обнаруживаем. Затем, после того, как мы выпрыгнем, мы можем попробовать умножить их и посмотреть, какие из них следует включить, а какие - исключить. Вот как это выглядит:
x = 1; // Exponent
bX = b; // b^x
powers = [b]; // b^{2^0}
exps = [1]; // 2^0
while (bX <= n) {
bX *= bX; // bX = bX^2
powers += bX; // Append bX
x++;
exps += x;
}
# Overshot, now recover the bits
resultExp = 1
result = 0;
while (x > 0) {
# If including this bit doesn't overshoot, it's part of the
# representation of x.
if (resultExp * powers[x] <= n) {
resultExp *= powers[x];
result += exps[x];
}
x--;
}
return result;
Это, конечно, более сложный подход, но он быстрее. Поскольку искомое значение равно ⌊b x ⌋, и мы по существу используем решение из «угадай игру чисел», чтобы выяснить, что такое x, количество умножений равно O (log log b n) с использованием памяти O (log log b n) для хранения промежуточных степеней. Это экспоненциально быстрее, чем в предыдущем решении!
Подход 3: Представления Зекендорфа
В предыдущем подходе есть небольшая модификация, которая сохраняет время выполнения O (журнал журнала b n) но уменьшает использование вспомогательного пространства до O (1). Идея состоит в том, что вместо записи показателя в двоичном виде с использованием регулярной системы мы выписываем число, используя теорема Цекендорфа , которая является двоичной системой счисления, основанной на последовательности Фибоначчи. Преимущество состоит в том, что вместо того, чтобы хранить промежуточные степени двух, мы можем использовать тот факт, что любых двух последовательных чисел Фибоначчи достаточно, чтобы позволить вам вычислить следующее или предыдущее число Фибоначчи, что позволяет нам восстанавливать степени b по мере необходимости. Вот реализация этой идеи в C ++.
Подход 4: Побитовое итерированное умножение
В некоторых случаях вам нужно найти логарифмы, где база журнала равна двум. В этом случае вы можете воспользоваться тем фактом, что числа на компьютере представлены в двоичном формате и что умножения и деления на два соответствуют сдвигам битов.
Например, давайте возьмем метод повторного умножения, сделанный ранее, где мы вычислили все большие и большие степени b, пока мы не опередили. Мы можем сделать ту же технику, используя битовые сдвиги, и она намного быстрее:
x = 0; # Exponent
while ((1 << x) <= n) {
x++;
}
return x - 1;
Этот подход все еще выполняется во времени O (log n), как и раньше, но, вероятно, быстрее реализуется таким образом, чем с умножениями, потому что Процессор может выполнять сдвиги битов намного быстрее.
Подход 5: Битовый двоичный поиск
Логарифм числа два в двоичном виде, записанный в двоичном формате, эквивалентен позиции наиболее значимого немного этого числа. Чтобы найти этот бит, мы можем использовать технику бинарного поиска, несколько напоминающую подход 2, но сделанный быстрее, потому что машина может обрабатывать несколько битов параллельно в одной инструкции. В основном, как и прежде, мы генерируем последовательность 2 2 0 , 2 2 1 , et c. пока мы не превысим число, давая верхнюю границу того, насколько высоким может быть старший бит. Оттуда мы делаем бинарный поиск, чтобы найти старший 1 бит. Вот как это выглядит:
x = 1;
while ((1 << x) <= n) {
x *= 2;
}
# We've overshot the high-order bit. Do a binary search to find it.
low = 0;
high = x;
while (low < high) {
mid = (low + high) / 2;
# Form a bitmask with 1s up to and including bit number mid.
# This can be done by computing 2^{m+1} - 1.
mask = (1 << (mid + 1)) - 1
# If the mask overlaps, branch higher
if (mask & n) {
low = mid + 1
}
# Otherwise, branch lower
else {
high = mid
}
}
return high - 1
Этот подход выполняется во времени O (log log n), поскольку двоичный поиск занимает время logarithmi c в искомом количестве и искомом количестве. for это O (log n). Он использует O (1) вспомогательное пространство.
Подход 6: Волшебный параллелизм на уровне слов
Ускорение в Подходе 5 во многом связано с тем, что мы можем тестировать несколько битов параллельно, используя одиночная побитовая операция. Делая поистине удивительные вещи с машинными словами , можно использовать этот параллелизм для поиска старшего значащего бита в числе во времени O (1) , используя только basi c арифметика c операций и битовых сдвигов, и делать это таким образом, чтобы среда выполнения полностью не зависела от размера машинного слова (например, алгоритм работает одинаково быстро на 16-битных, 32-битных и 64-битных немного машинка). Используемые методы довольно сложны, и я признаюсь, что я понятия не имел, что это было возможно сделать до недавнего времени, когда я изучал эту технику при преподавании курса продвинутых структур данных.
Резюме
Подводя итог Вот перечисленные подходы, их временная сложность и пространственная сложность.
Approach Which Bases? Time Complexity Space Complexity
--------------------------------------------------------------------------
Iter. Multiplication Any O(log_b n) O(1)
Repeated Squaring Any O(log log_b n) O(log log_b n)
Zeckendorf Logarithm Any O(log log_b n) O(1)
Bitwise Multiplication 2 O(log n) O(1)
Bitwise Binary Search 2 O(log log n) O(1)
Word-Level Parallelism 2 O(1) O(1)
Есть много других алгоритмов, которые я не упомянул здесь, которые стоит изучить. Некоторые алгоритмы работают, сегментируя машинные слова на блоки некоторого фиксированного размера, предварительно вычисляя позицию первого 1 бита в каждом блоке, а затем проверяя один блок за раз. Эти подходы имеют время выполнения, которое зависит от размера машинного слова, и (насколько мне известно) ни один из них не асимптотически быстрее, чем подходы, которые я изложил здесь. Другие подходы работают с использованием того факта, что некоторые процессоры имеют инструкции, которые немедленно выводят позицию старшего значащего бита в числе, или работают с использованием аппаратного обеспечения с плавающей запятой. Это также интересно и увлекательно, обязательно ознакомьтесь с ними!
Еще одна область, которую стоит изучить, - это наличие целых чисел произвольной точности. Там затраты на умножения, деления, сдвиги и т. Д. c. не O (1), и относительная стоимость этих алгоритмов изменяется. Это, безусловно, заслуживает более детального изучения, если вам интересно!
Включенный здесь код написан в псевдокоде, потому что он предназначен в основном для демонстрации. В реальной реализации вам нужно беспокоиться о переполнении, обрабатывая случай, когда входные данные отрицательны или равны нулю и т. Д. c. Просто к вашему сведению. : -)
Надеюсь, это поможет!