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

**Рисунок 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).

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

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

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

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

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

Нахождение триангуляции Делоне набора точек, зная евклидово минимальное остовное дерево : рандомизированное 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. дои : 10.3390/a12080159 . МР 3998658 .
^ Девиллерс, Оливье (март 1992 г.). «Рандомизация дает простой $O(n\log ^{\ast }n)$ алгоритмы для сложных $\Omega (n)$ проблемы» (PDF) . Международный журнал вычислительной геометрии и приложений . 2 (1): 97–111. : cs /9810007 . doi : 10.1142/S021819599200007X . MR 1159844. . S2CID 60203 arXiv
^ Алон, Нога ; Азар, Йоси (апрель 1989 г.). «Нахождение приблизительного максимума» (PDF) . SIAM Journal по вычислительной технике . 18 (2): 258–267. дои : 10.1137/0218017 . МР 0986665 .
^ Коул, Ричард ; Вишкин, Узи (июль 1986 г.). «Детерминированное подбрасывание монеты с применением оптимального ранжирования в параллельных списках» (PDF) . Информация и контроль . 70 (1): 32–53. дои : 10.1016/S0019-9958(86)80023-7 . МР 0853994 .
^ Сантанам, Рахул (2001). «О сепараторах, сегрегаторах и времени и пространстве» (PDF) . Материалы 16-й ежегодной конференции IEEE по сложности вычислений, Чикаго, Иллинойс, США, 18–21 июня 2001 г. Компьютерное общество IEEE . стр. 286–294. дои : 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. дои : 10.3390/a12080159 . МР 3998658 .

[3] Девиллерс, Оливье (март 1992 г.). «Рандомизация дает простой $O(n\log ^{\ast }n)$ алгоритмы для сложных $\Omega (n)$ проблемы» (PDF) . Международный журнал вычислительной геометрии и приложений . 2 (1): 97–111. : cs /9810007 . doi : 10.1142/S021819599200007X . MR 1159844. . S2CID 60203 arXiv

[4] Алон, Нога ; Азар, Йоси (апрель 1989 г.). «Нахождение приблизительного максимума» (PDF) . SIAM Journal по вычислительной технике . 18 (2): 258–267. дои : 10.1137/0218017 . МР 0986665 .

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

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

[1]

[2]

[3]

[4]

[5]

[6]