Iterated logarithm

Iterated logarithm

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

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

or, in pseudocode:

function iterLog("real" n) if n ≤ 1 return 0 else return 1 + iterLog(log(n))

or, in iterative pseudocode:

function iterLog("real" n) i = 0 while n > 1 n = log(n) i = i + 1 return i

or, on the positive real numbers, the continuous super-logarithm (an inverse function of tetration) definition is equivalent::log^* n = lceil ext{slog}_e(n) ceilbut on the negative real numbers, log-star is 0, whereas lceil ext{slog}_e(-x) ceil = -1 for positive "x", so the two functions differ for negative arguments.

In computer science, lg* is often used to indicate the binary iterated logarithm, which iterates the binary logarithm instead. 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 [0, 1] on the "x"-axis.

Mathematically, the iterated logarithm is well-defined not only for base 2 and base "e", but for any base greater than e^{1/e}approx1.444667.

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 one must replace the number by the sum of its digits before reaching its digital root.

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, Olivier Devillers
* Fürer's algorithm for integer multiplication: O("n" log "n" 2lg* "n")
* Finding an approximate maximum (element at least as large as the median): lg* "n" − 4 to lg* "n" + 2 parallel operations [Noga Alon and Yossi Azar, "Finding an Approximate Maximum". "SIAM Journal of Computing" 18:2 (1989), pp. 258–267.]

The iterated logarithm is an extremely slowly-growing function, much more slowly than the logarithm itself; for all practical values of "n" (less or equal than 265536, which is far more than the number of particles in the universe), even the iterated logarithm to the base 2 is less or equal than 5.

Higher bases give smaller iterated logarithms. Indeed, the only function used in complexity theory that grows more slowly is the inverse of the Ackermann function.

References

*Introduction to Algorithms|2|chapter=3.2: Standard notations and common functions|pages=pp. 55–56


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Law of the iterated logarithm — In probability theory,the law of the iterated logarithm is the name given to several theorems which describe the magnitude of the fluctuations of a random walk.The original statement (1924) of the law of the iterated logarithm is due to A. Y.… …   Wikipedia

  • Logarithm — The graph of the logarithm to base 2 crosses the x axis (horizontal axis) at 1 and passes through the points with coordinates (2, 1), (4, 2), and (8, 3) …   Wikipedia

  • Super-logarithm — In mathematics, the super logarithm is one of the two inverse functions of tetration. Just as exponentiation has two inverse functions: roots and logarithms, likewise tetration has two inverse functions: super roots and super logarithms. There… …   Wikipedia

  • List of logarithm topics — This is a list of logarithm topics, by Wikipedia page. See also the list of exponential topics.*Acoustic power *antilogarithm *Apparent magnitude *Bel *Benford s law *Binary logarithm *Bode plot *Henry Briggs *Cologarithm *Common logarithm… …   Wikipedia

  • Ultra exponential function — Articleissues OR=January 2008 other=This article uses nonstandard notations, which are confusing and superfluous.In mathematics the ultra exponential function is a special case of the iterated exponential function more commonly known as tetration …   Wikipedia

  • List of mathematics articles (I) — NOTOC Ia IA automorphism ICER Icosagon Icosahedral 120 cell Icosahedral prism Icosahedral symmetry Icosahedron Icosian Calculus Icosian game Icosidodecadodecahedron Icosidodecahedron Icositetrachoric honeycomb Icositruncated dodecadodecahedron… …   Wikipedia

  • List of mathematical functions — In mathematics, several functions or groups of functions are important enough to deserve their own names. This is a listing of pointers to those articles which explain these functions in more detail. There is a large theory of special functions… …   Wikipedia

  • Random walk — A random walk, sometimes denoted RW, is a mathematical formalization of a trajectory that consists of taking successive random steps. The results of random walk analysis have been applied to computer science, physics, ecology, economics and a… …   Wikipedia

  • List of mathematics articles (L) — NOTOC L L (complexity) L BFGS L² cohomology L function L game L notation L system L theory L Analyse des Infiniment Petits pour l Intelligence des Lignes Courbes L Hôpital s rule L(R) La Géométrie Labeled graph Labelled enumeration theorem Lack… …   Wikipedia

  • Logarithmic growth — In mathematics, logarithmic growth describes a phenomenon that whose size or cost can be described as a logarithm function of some input. e.g. y = C log ( x ). Note that any logarithm base can be used, since one can be converted to another by a… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”