Iterated logarithm

Incomputer science,theiterated logarithmof $n$ ,writtenlog* $n$ (usually read "log star"), is the number of times thelogarithmfunction must beiterativelyapplied before the result is less than or equal to $1$ .^[1]The simplest formal definition is the result of thisrecurrence relation:

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

In computer science,lg*is often used to indicate thebinary iterated logarithm,which iterates thebinary logarithm(with base $2$ ) instead of the natural logarithm (with basee). Mathematically, the iterated logarithm is well defined for any base greater than $e^{1/e}\approx 1.444667$ ,not only for base $2$ and basee.The "super-logarithm" function $\mathrm {slog} _{b}(n)$ is "essentially equivalent" to the base $b$ iterated logarithm (although differing in minor details ofrounding) and forms an inverse to the operation oftetration.^[2]

Analysis of algorithms

The iterated logarithm is useful inanalysis of algorithmsandcomputational complexity,appearing in the time and space complexity bounds of some algorithms such as:

Finding theDelaunay triangulationof a set of points knowing theEuclidean minimum spanning tree:randomizedO(nlog*n) time.^[3]
Fürer's algorithmfor integer multiplication: O(nlogn2^O(lg*n)).
Finding an approximate maximum (element at least as large as the median):lg*n− 1 ± 3 parallel operations.^[4]
Richard Cole andUzi Vishkin'sdistributed algorithm for 3-coloring ann-cycle:O(log*n) synchronous communication rounds.^[5]

The iterated logarithm grows at an extremely slow rate, much slower than the logarithm itself, or repeats of it. This is because the tetration grows much faster than iterated exponential:

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

the inverse grows much slower: $\log _{b}^{*}x\ll \log _{b}^{n}x$ .

For all values ofnrelevant to counting the running times of algorithms implemented in practice (i.e.,n≤ 2⁶⁵⁵³⁶,which is far more than the estimated number of atoms in the known universe), the iterated logarithm with base 2 has a value no more than 5.

The base-2 iterated logarithm
x	lg*x
$(-\infty, 1]$	0
$(1, 2]$	1
$(2, 4]$	2
$(4, 16]$	3
$(16, 65536]$	4
$(65536, 2 65536]$	5

Higher bases give smaller iterated logarithms.

Other applications

The iterated logarithm is closely related to thegeneralized logarithm functionused insymmetric level-index arithmetic.The additivepersistence of a number,the number of times someone must replace the number by the sum of its digits before reaching itsdigital root,is $O(\log ^{*}n)$ .

Incomputational complexity theory,Santhanam^[6]shows that thecomputational resources DTIME—computation timefor adeterministic Turing machine— andNTIME— computation time for anon-deterministic Turing machine— are distinct up to $n{\sqrt {\log ^{*}n}}.$

References

^Cormen, Thomas H.;Leiserson, Charles E.;Rivest, Ronald L.;Stein, Clifford(2009) [1990]. "The iterated logarithm function, in Section 3.2: Standard notations and common functions".Introduction to Algorithms(3rd ed.). MIT Press and McGraw-Hill. pp. 58–59.ISBN 0-262-03384-4.
^Furuya, Isamu; Kida, Takuya (2019)."Compaction of Church numerals".Algorithms.12(8) 159: 159.doi:10.3390/a12080159.MR 3998658.
^Devillers, Olivier (March 1992)."Randomization yields simple $O(n\log ^{\ast }n)$ algorithms for difficult $\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.
^Alon, Noga;Azar, Yossi (April 1989)."Finding an approximate maximum"(PDF).SIAM Journal on Computing.18(2): 258–267.doi:10.1137/0218017.MR 0986665.
^Cole, Richard;Vishkin, Uzi(July 1986)."Deterministic coin tossing with applications to optimal parallel list ranking"(PDF).Information and Control.70(1): 32–53.doi:10.1016/S0019-9958(86)80023-7.MR 0853994.
^Santhanam, Rahul (2001)."On separators, segregators and time versus space"(PDF).Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001.IEEE Computer Society.pp. 286–294.doi:10.1109/CCC.2001.933895.ISBN 0-7695-1053-1.

[1] Cormen, Thomas H.;Leiserson, Charles E.;Rivest, Ronald L.;Stein, Clifford(2009) [1990]. "The iterated logarithm function, in Section 3.2: Standard notations and common functions".Introduction to Algorithms(3rd ed.). MIT Press and McGraw-Hill. pp. 58–59.ISBN 0-262-03384-4.

[2] Furuya, Isamu; Kida, Takuya (2019)."Compaction of Church numerals".Algorithms.12(8) 159: 159.doi:10.3390/a12080159.MR 3998658.

[3] Devillers, Olivier (March 1992)."Randomization yields simple $O(n\log ^{\ast }n)$ algorithms for difficult $\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] Alon, Noga;Azar, Yossi (April 1989)."Finding an approximate maximum"(PDF).SIAM Journal on Computing.18(2): 258–267.doi:10.1137/0218017.MR 0986665.

[5] Cole, Richard;Vishkin, Uzi(July 1986)."Deterministic coin tossing with applications to optimal parallel list ranking"(PDF).Information and Control.70(1): 32–53.doi:10.1016/S0019-9958(86)80023-7.MR 0853994.

[6] Santhanam, Rahul (2001)."On separators, segregators and time versus space"(PDF).Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001.IEEE Computer Society.pp. 286–294.doi:10.1109/CCC.2001.933895.ISBN 0-7695-1053-1.

[1]

[2]

[3]

[4]

[5]

[6]

Analysis of algorithms

Other applications

See also

References