Iterated logarithm

{{For|the theorem in probability theory|Law of the iterated logarithm}}

In computer science, the iterated logarithm of $n$ , written {{log-star}} $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 $1$ .{{Introduction to Algorithms|3|chapter=The iterated logarithm function, in Section 3.2: Standard notations and common functions|pages=58–59}} The simplest formal definition is the result of this recurrence relation:

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

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

| last1 = Furuya | first1 = Isamu

| last2 = Kida | first2 = Takuya

| doi = 10.3390/a12080159

| issue = 8

| journal = Algorithms

| mr = 3998658

| article-number = 159

| title = Compaction of Church numerals

| volume = 12

| year = 2019| page = 159

| doi-access = free

}}

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-star}} n) time.{{cite journal

| last = Devillers | first = Olivier

| doi = 10.1142/S021819599200007X

| journal = International Journal of Computational Geometry & Applications

| volume = 2 | issue = 1

| date = March 1992

| pages = 97–111

| mr = 1159844

| title = Randomization yields simple $O(n\log^\ast n)$ algorithms for difficult $\Omega(n)$ problems

| s2cid = 60203

| arxiv = cs/9810007

| url = https://inria.hal.science/file/index/docid/167206/filename/hal.pdf

}}

Fürer's algorithm for integer multiplication: O(n log n 2^{O({{log-star|lg}} n)}).
Finding an approximate maximum (element at least as large as the median): {{log-star|lg}} n − 1 ± 3 parallel operations.{{cite journal

| last1 = Alon | first1 = Noga | author1-link = Noga Alon

| last2 = Azar | first2 = Yossi

| doi = 10.1137/0218017

| journal = SIAM Journal on Computing

| volume = 18 | issue = 2

| date = April 1989

| pages = 258–267

| mr = 986665

| title = Finding an approximate maximum

| url = https://web.math.princeton.edu/~nalon/PDFS/Publications2/Finding%20an%20approximate%20maximum.pdf

}}

Richard Cole and Uzi Vishkin's distributed algorithm for 3-coloring an n-cycle: O({{log-star}} n) synchronous communication rounds.{{cite journal

| last1 = Cole | first1 = Richard | author1-link = Richard J. Cole

| last2 = Vishkin | first2 = Uzi | author2-link = Uzi Vishkin

| doi = 10.1016/S0019-9958(86)80023-7 | doi-access = free

| journal = Information and Control

| volume = 70 | issue = 1

| pages = 32–53

| mr = 853994

| title = Deterministic coin tossing with applications to optimal parallel list ranking

| date = July 1986

| url = https://archive.org/download/deterministiccoi00vish/deterministiccoi00vish.pdf

}}

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 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.

class=wikitable \|+The base-2 iterated logarithm ! x !! {{lg-star}} x
{{open-closed\|−∞, 1}}	0
{{open-closed\|1, 2}}	1
{{open-closed\|2, 4}}	2
{{open-closed\|4, 16}}	3
{{open-closed\|16, 65536}}	4
{{open-closed\|65536, 2⁶⁵⁵³⁶}}	5

Higher bases give smaller iterated logarithms.

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 $O(\log^* n)$ .

In computational complexity theory, Santhanam{{cite conference

| last = Santhanam | first = Rahul

| contribution = On separators, segregators and time versus space

| contribution-url = https://scholar.archive.org/work/jsi2cizbpbcsrkq3annbprthsm/access/wayback/http://homepages.inf.ed.ac.uk/rsanthan/Papers/segsepfinal.pdf

| doi = 10.1109/CCC.2001.933895

| pages = 286–294

| publisher = IEEE Computer Society

| title = Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001

| title-link = Computational Complexity Conference

| year = 2001| isbn = 0-7695-1053-1

}} 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 $n\sqrt{\log^*n}.$

References

Category:Asymptotic analysis

Category:Logarithms

class=wikitable \|+The base-2 iterated logarithm ! x !! {{lg-star}} x
{{open-closed\|−∞, 1}}	0
{{open-closed\|1, 2}}	1
{{open-closed\|2, 4}}	2
{{open-closed\|4, 16}}	3
{{open-closed\|16, 65536}}	4
{{open-closed\|65536, 2⁶⁵⁵³⁶}}	5

Iterated logarithm

Analysis of algorithms

Other applications

See also

References