Iterated logarithm

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

In computer science, the iterated logarithm of , written log*  (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 . The simplest formal definition is the result of this recurrence relation:

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

i.e. the base b iterated logarithm is if n lies within the interval , where denotes tetration. However, on the negative real numbers, log-star is , whereas for positive , 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 = logb(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, logb(n) ), to (0, logb(n) ), to (logb(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 on the x-axis.

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

Mathematically, the iterated logarithm is well-defined for any base greater than , not only for base and base e.

Analysis of algorithms[edit]

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:

The iterated logarithm grows at an extremely slow rate, much slower than the logarithm itself. For all values of n relevant to counting the running times of algorithms implemented in practice (i.e., n ≤ 265536, 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.

Other applications[edit]

The iterated logarithm is closely related to the generalized logarithm function used in symmetric level-index arithmetic. It is also proportional to 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.

In computational complexity theory, Santhanam[6] shows that the computational resources DTIMEcomputation time for a deterministic Turing machine — and NTIME — computation time for a non-deterministic Turing machine — are distinct up to

Notes[edit]

  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. 97–111.
  2. ^ Noga Alon and Yossi Azar, "Finding an Approximate Maximum". SIAM Journal on Computing 18:2 (1989), pp. 258–267.
  3. ^ Richard Cole and Uzi Vishkin: "Deterministic coin tossing with applications to optimal parallel list ranking", Information and Control 70:1(1986), pp. 32–53.
  4. ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill. ISBN 0-262-03141-8. Section 30.5.
  5. ^ https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf
  6. ^ On Separators, Segregators and Time versus Space

References[edit]