Iterated logarithm

For the theorem in probability theory, see Law of the iterated logarithm.

In computer science, the iterated logarithm of ${\displaystyle n}$, written log*  ${\displaystyle n}$ (usually read "log star"), is the number of times the logarithm function must be iteratively applied before the result is less than or equal to ${\displaystyle 1}$. ^[1] The simplest formal definition is the result of this recurrence relation:

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

On the positive real numbers, the continuous super-logarithm (inverse tetration) is essentially equivalent:

${\displaystyle \log ^{*}n=\lceil \mathrm {slog} _{e}(n)\rceil }$

i.e. the base b iterated logarithm is ${\displaystyle \log ^{*}n=y}$ if n lies within the interval ${\displaystyle ^{y-1}b<n\leq \ ^{y}b}$, where ${\displaystyle {^{y}b}=\underbrace {b^{b^{\cdot ^{\cdot ^{b}}}}} _{y}}$denotes tetration. However, on the negative real numbers, log-star is ${\displaystyle 0}$, whereas ${\displaystyle \lceil {\text{slog}}_{e}(-x)\rceil =-1}$ for positive ${\displaystyle x}$, so the two functions differ for negative arguments.

Figure 1. Demonstrating log* 4 = 2 for the base-e iterated logarithm. The value of the iterated logarithm can be found by "zig-zagging" on the curve y = log_b(x) from the input n, to the interval [0,1]. In this case, b = e. The zig-zagging entails starting from the point (n, 0) and iteratively moving to (n, log_b(n) ), to (0, log_b(n) ), to (log_b(n), 0 ).

The iterated logarithm accepts any positive real number and yields an integer. Graphically, it can be understood as the number of "zig-zags" needed in Figure 1 to reach the interval ${\displaystyle [0,1]}$ on the x-axis.

In computer science, lg* is often used to indicate the binary iterated logarithm, which iterates the binary logarithm (with base ${\displaystyle 2}$) instead of the natural logarithm (with base e).

Mathematically, the iterated logarithm is well-defined for any base greater than ${\displaystyle e^{1/e}\approx 1.444667}$, not only for base ${\displaystyle 2}$ and base e.

Analysis of algorithms

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

• Finding the Delaunay triangulation of a set of points knowing the Euclidean minimum spanning tree: randomized O(n  log*  n) time. ^[2]
• Fürer's algorithm for integer multiplication: O(n log n 2^{O(lg*  n)}).
• Finding an approximate maximum (element at least as large as the median): lg*  n − 1 ± 3 parallel operations. ^[3]
• Richard Cole and Uzi Vishkin's distributed algorithm for 3-coloring an n-cycle: O(log*  n) synchronous communication rounds. ^[4]

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:

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

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

For all values of n relevant 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
(−∞, 1]	0
(1, 2]	1
(2, 4]	2
(4, 16]	3
(16, 65536]	4
(65536, 265536]	5

Higher bases give smaller iterated logarithms. Indeed, the only function commonly used in complexity theory that grows more slowly is the inverse Ackermann function ^{[ citation needed ]}.

Other applications

The iterated logarithm is closely related to the generalized logarithm function used in symmetric level-index arithmetic. The additive persistence of a number, the number of times someone must replace the number by the sum of its digits before reaching its digital root, is ${\displaystyle O(\log ^{*}n)}$.

In computational complexity theory, Santhanam ^[5] shows that the computational resources DTIME — computation time for a deterministic Turing machine — and NTIME — computation time for a non-deterministic Turing machine — are distinct up to ${\displaystyle n{\sqrt {\log ^{*}n}}.}$

References

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. Devillers, Olivier (March 1992). "Randomization yields simple ${\displaystyle O(n\log ^{\ast }n)}$ algorithms for difficult ${\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.
3. 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.
4. 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.
5. 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.