View source for Iterated logarithm

{{Short description|Inverse function to a tower of powers}}
{{For|the theorem in probability theory|Law of the iterated logarithm}}
[[Image:Iterated logarithm.png|right|300px|thumb|'''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<sub>b</sub>(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<sub>b</sub>(n) ), to (0, log<sub>b</sub>(n) ), to (log<sub>b</sub>(n), 0 ).]]
In [[computer science]], the '''iterated logarithm''' of <math>n</math>, written {{log-star}}&nbsp;<math>n</math> (usually read "'''log star'''"), is the number of times the [[logarithm]] function must be  [[iteration|iteratively]] applied before the result is less than or equal to <math>1</math>.<ref>{{Introduction to Algorithms|3|chapter=The iterated logarithm function, in Section 3.2: Standard notations and common functions|pages=58–59}}</ref> The simplest formal definition is the result of this [[recurrence relation]]:

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

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

==Analysis of algorithms==
The iterated logarithm is useful in [[analysis of algorithms]] and [[computational complexity theory|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 [[Big-O notation|O]](''n''&nbsp;{{log-star}}&nbsp;''n'') time.<ref>{{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 <math>O(n\log^\ast n)</math> algorithms for difficult <math>\Omega(n)</math> problems
 | s2cid = 60203
 | arxiv = cs/9810007
 | url = https://inria.hal.science/file/index/docid/167206/filename/hal.pdf
 }}</ref>
* [[Fürer's algorithm]] for integer multiplication: O(''n''&nbsp;log&nbsp;''n''&nbsp;2<sup>''O''({{log-star|lg}}&nbsp;''n'')</sup>).
* Finding an approximate maximum (element at least as large as the median): {{log-star|lg}}&nbsp;''n'' − 1 ± 3 parallel operations.<ref>{{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
 }}</ref>
* Richard Cole and [[Uzi Vishkin]]'s [[Graph coloring#Parallel and distributed algorithms|distributed algorithm for 3-coloring an ''n''-cycle]]: ''O''({{log-star}}&nbsp;''n'') synchronous communication rounds.<ref>{{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
 }}</ref>

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:

<math display="block">{^{y}b} = \underbrace{b^{b^{\cdot^{\cdot^{b}}}}}_y \gg \underbrace{b^{b^{\cdot^{\cdot^{b^{y}}}}}}_n</math>

the inverse grows much slower: <math>\log_b^* x \ll \log_b^n x</math>.

For all values of ''n'' relevant to counting the running times of algorithms implemented in practice (i.e., ''n''&nbsp;≤&nbsp;2<sup>65536</sup>, 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}}&nbsp;''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<sup>65536</sup>}} || 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 <math>O(\log^* n)</math>.

In [[computational complexity theory]], Santhanam<ref>{{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
 }}</ref> shows that the [[computational resource]]s [[DTIME]] — [[time complexity|computation time]] for a [[Turing machine|deterministic Turing machine]] — and [[NTIME]] — computation time for a [[non-deterministic Turing machine]] — are distinct up to <math>n\sqrt{\log^*n}.</math>

==See also==
*[[Ackermann function#Inverse|Inverse Ackermann function]], an even more slowly growing function also used in computational complexity theory

==References==
{{reflist}}

{{Authority control}}

[[Category:Asymptotic analysis]]
[[Category:Logarithms]]