Iterated Logarithm

Decimal

\scriptstyle {\lg *4=2}

{\ displaystyle \ scriptstyle {\ lg * 4 = 2}}

{\ displaystyle \ scriptstyle {\ lg * 4 = 2}}

Iterated Logarithm $\log ^{*}n$ ${\ displaystyle \ log ^ {*} n}$ ${\ displaystyle \ log ^ {*} n}$ in mathematics and computer science it is defined as an integer function equal to the number of iterative logarithms of the argument necessary for the result to become less than or equal to 1 . This function is defined for all positive numbers, but in applications, the argument is usually a natural number . A more strictly iterated logarithm is determined by a recursive formula:

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

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

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

Iterated logarithm defined for bases $b>e^{1/e}\approx 1{,}444667$ ${\ displaystyle b> e ^ {1 / e} \ approx 1 {,} 444667}$ ${\ displaystyle b> e ^ {1 / e} \ approx 1 {,} 444667}$ A073229 . If positive $b<e^{1/e}$ ${\ displaystyle b <e ^ {1 / e}}$ ${\ displaystyle b <e ^ {1 / e}}$ , then its recursive sequence converges to a number greater than 1.

Computer science usually uses a binary iterated logarithm. This function grows unlimitedly, but extremely slowly. For all arguments conceivable in practice, it could be replaced by a constant, but for formulas defined on the entire numerical axis, such a record would be erroneous. The values of the binary iterated logarithm for all practically interesting arguments do not exceed 5 and are given below.

n	$\log _{2}^{}n$ ${\ displaystyle \ log _ {2} ^ {} n}$ ${\ displaystyle \ log _ {2} ^ {*} n}$
(−∞, 1]	0
(12]	one
(2, 4]	2
(4, 16]	3
(16, 65536]	four
(65536, 2 ⁶⁵⁵³⁶ (~ 10 ¹⁹⁶⁶⁰ )]	five

Application

The iterated logarithm arises in the analysis of some algorithms in estimates of their computational complexity ^[1] ^[2] ^[3] ^[4] ^[5] The most famous estimate of the time complexity of the Fuhrer algorithm for multiplying integers is $O(n\log n\cdot 2^{O(\log ^{*}n)})$ ${\ displaystyle O (n \ log n \ cdot 2 ^ {O (\ log ^ {*} n)})}$ $O(n\log n\cdot 2^{O(\log ^{*}n)})$ , and an estimate for the 3-coloring algorithm $n$ ${\ displaystyle n}$ $n$ -cycle in the graph - $O(\log ^{*}n)$ ${\ displaystyle O (\ log ^ {*} n)}$ $O(\log ^{*}n)$ ^[6]

Notes

↑ Olivier Devillers, “Randomization yields simple O (n log * n) algorithms for difficult ω (n) problems.” International Journal of Computational Geometry & Applications 2 : 01 (1992), pp. 971-11.
↑ Noga Alon and Yossi Azar, “Finding an Approximate Maximum.” SIAM Journal of Computing 18 : 2 (1989), pp. 2582–67.
↑ On Separators, Segregators and Time versus Space
↑ https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf
↑ Schneider, J. (2008), "A log-star distributed maximal independent set algorithm for growth-bounded graphs" , Proceedings of the Symposium on Principles of Distributed Computing
↑ Richard Cole and Uzi Vishkin: “Deterministic coin tossing with applications to optimal parallel list ranking”, Information and Control 70: 1 (1986), pp. 325-3.

[1] Olivier Devillers, “Randomization yields simple O (n log * n) algorithms for difficult ω (n) problems.” International Journal of Computational Geometry & Applications 2 : 01 (1992), pp. 971-11.

[2] Noga Alon and Yossi Azar, “Finding an Approximate Maximum.” SIAM Journal of Computing 18 : 2 (1989), pp. 2582–67.

[3] On Separators, Segregators and Time versus Space

[4] ttps://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf

[5] Schneider, J. (2008), "A log-star distributed maximal independent set algorithm for growth-bounded graphs" , Proceedings of the Symposium on Principles of Distributed Computing

[6] Richard Cole and Uzi Vishkin: “Deterministic coin tossing with applications to optimal parallel list ranking”, Information and Control 70: 1 (1986), pp. 325-3.

Iterated Logarithm

Application

Notes

More articles: