Повторный логарифм

Обратная функция к башне степеней

**Рисунок 1.** Демонстрация log* 4 = 2 для итерационного логарифма по основанию e. Значение итерационного логарифма можно найти, "зигзагообразно" перемещаясь по кривой y = log _b (x) от входного значения n до интервала [0,1]. В этом случае b = e. Зигзагообразный ход подразумевает начало от точки (n, 0) и итеративное перемещение к (n, log _b (n) ), к (0, log _b (n) ), к (log _b (n), 0 ).

В информатике итеративный логарифм , обозначаемый как log* (обычно читается как « log star »), — это число раз, которое логарифмическая функция должна быть применена итеративно, прежде чем результат станет меньше или равен . ^[1] Простейшее формальное определение — это результат этого рекуррентного соотношения : $n$ $n$ $1$

\log ^{*}n:={\begin{cases}0&{\mbox{if }}n\leq 1;\\1+\log ^{*}(\log n)&{\mbox{if }}n>1\end{cases}}

В информатике lg * часто используется для обозначения двоичного итерированного логарифма , который итерирует двоичный логарифм (с основанием ) вместо натурального логарифма (с основанием e ). Математически итерированный логарифм хорошо определен для любого основания, большего , а не только для основания и основания e . Функция «суперлогарифм» «по существу эквивалентна» основанию итерированного логарифма (хотя отличается незначительными деталями округления ) и образует обратную операцию к тетрации . [ ^2] $2$ $e^{1/e}\приблизительно 1,444667$ $2$ $\mathrm {slog} _{b}(n)$ $б$

Анализ алгоритмов

Итеративный логарифм полезен при анализе алгоритмов и вычислительной сложности , появляясь в ограничениях временной и пространственной сложности некоторых алгоритмов, таких как:

Нахождение триангуляции Делоне для набора точек, зная минимальное евклидово остовное дерево : рандомизированное время O ( n log* n ). ^[3]
Алгоритм Фюрера для целочисленного умножения: O( n log n 2 ^{O (lg* n )} ).
Нахождение приблизительного максимума (элемент, по крайней мере, такой же большой, как медиана): lg* n − 1 ± 3 параллельных операций. ^[4]
Распределенный алгоритм Ричарда Коула и Узи Вишкина для 3-цветной раскраски в n- цикле : O (log* n ) синхронных раундов связи. ^[5]

Итерированный логарифм растет чрезвычайно медленно, гораздо медленнее, чем сам логарифм или его повторения. Это происходит потому, что тетрация растет гораздо быстрее, чем итерированная экспонента:

${^{y}b}=\underbrace {b^{b^{\cdot ^{\cdot ^{b}}}}} _{y}\gg \underbrace {b^{b^{\cdot ^{\cdot ^{b^{y}}}}}} _{n}$

обратная величина растет гораздо медленнее: . $\log _{b}^{*}x\ll \log _{b}^{n}x$

Для всех значений n , имеющих отношение к подсчету времени работы алгоритмов, реализованных на практике (т. е. n ≤ 2 ⁶⁵⁵³⁶ , что намного больше предполагаемого числа атомов в известной Вселенной), итерированный логарифм с основанием 2 имеет значение не более 5.

Повторный логарифм по основанию 2
х	лг * х
$(-\infty, 1]$	0
$(1, 2]$	1
$(2, 4]$	2
$(4, 16]$	3
$(16, 65536]$	4
$(65536, 2 65536]$	5

Более высокие основания дают меньшие повторные логарифмы.

Другие приложения

Итерированный логарифм тесно связан с функцией обобщенного логарифма , используемой в симметричной уровневой арифметике . Аддитивная устойчивость числа , количество раз, которое кто-то должен заменить число суммой его цифр, прежде чем достичь его цифрового корня , равна . $O(\log ^{*}n)$

В теории вычислительной сложности Сантханам ^[6] показывает, что вычислительные ресурсы DTIME — время вычислений для детерминированной машины Тьюринга — и NTIME — время вычислений для недетерминированной машины Тьюринга — различны с точностью до $n{\sqrt {\log ^{*}n}}.$

Смотрите также

Обратная функция Аккермана , еще более медленно растущая функция, также используемая в теории сложности вычислений.

Ссылки

^ Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л.; Стайн , Клиффорд (2009) [1990]. «Функция итерированного логарифма, в разделе 3.2: Стандартные обозначения и общие функции». Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. стр. 58–59. ISBN 0-262-03384-4.
^ Фуруя, Исаму; Кида, Такуя (2019). «Уплотнение чисел Чёрча». Алгоритмы . 12 (8) 159: 159. doi : 10.3390/a12080159 . MR 3998658.
^ Devillers, Olivier (март 1992). "Randomization yields simple O ( n log ∗ ⁡ n ) {\displaystyle O(n\log ^{\ast }n)} algorithms for difficulty Ω ( n ) {\displaystyle \Omega (n)} problems" (PDF) . International Journal of Computational Geometry & Applications . 2 (1): 97–111. arXiv : cs/9810007 . doi :10.1142/S021819599200007X. MR 1159844. S2CID 60203.
^ Алон, Нога ; Азар, Йосси (апрель 1989 г.). «Поиск приближенного максимума» (PDF) . SIAM Journal on Computing . 18 (2): 258–267. doi :10.1137/0218017. MR 0986665.
^ Коул, Ричард ; Вишкин, Узи (июль 1986 г.). «Детерминированное подбрасывание монеты с применением к оптимальному параллельному ранжированию списков» (PDF) . Информация и управление . 70 (1): 32–53. doi : 10.1016/S0019-9958(86)80023-7 . MR 0853994.
^ Santhanam, Rahul (2001). "О сепараторах, сегрегаторах и времени против пространства" (PDF) . Труды 16-й ежегодной конференции IEEE по вычислительной сложности, Чикаго, Иллинойс, США, 18-21 июня 2001 г. IEEE Computer Society . стр. 286–294. doi :10.1109/CCC.2001.933895. ISBN 0-7695-1053-1.

[1] Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л.; Стайн , Клиффорд (2009) [1990]. «Функция итерированного логарифма, в разделе 3.2: Стандартные обозначения и общие функции». Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. стр. 58–59. ISBN 0-262-03384-4.

[2] Фуруя, Исаму; Кида, Такуя (2019). «Уплотнение чисел Чёрча». Алгоритмы . 12 (8) 159: 159. doi : 10.3390/a12080159 . MR 3998658.

[3] Devillers, Olivier (март 1992). "Randomization yields simple O ( n log ∗ ⁡ n ) {\displaystyle O(n\log ^{\ast }n)} algorithms for difficulty Ω ( n ) {\displaystyle \Omega (n)} problems" (PDF) . International Journal of Computational Geometry & Applications . 2 (1): 97–111. arXiv : cs/9810007 . doi :10.1142/S021819599200007X. MR 1159844. S2CID 60203.

[4] Алон, Нога ; Азар, Йосси (апрель 1989 г.). «Поиск приближенного максимума» (PDF) . SIAM Journal on Computing . 18 (2): 258–267. doi :10.1137/0218017. MR 0986665.

[5] Коул, Ричард ; Вишкин, Узи (июль 1986 г.). «Детерминированное подбрасывание монеты с применением к оптимальному параллельному ранжированию списков» (PDF) . Информация и управление . 70 (1): 32–53. doi : 10.1016/S0019-9958(86)80023-7 . MR 0853994.

[6] Santhanam, Rahul (2001). "О сепараторах, сегрегаторах и времени против пространства" (PDF) . Труды 16-й ежегодной конференции IEEE по вычислительной сложности, Чикаго, Иллинойс, США, 18-21 июня 2001 г. IEEE Computer Society . стр. 286–294. doi :10.1109/CCC.2001.933895. ISBN 0-7695-1053-1.