Iterated logarithm

The title of this article is ambiguous. For the use of the term in probability theory, see Law of the iterated logarithm .

The iterated logarithm of a positive number n , denoted by (pronounced “log star of n”), indicates how often the logarithm function has to be used so that the result is less than or equal to 1. ${\displaystyle \log ^{*}n}$

definition

Formally, the iterated logarithmic function , which assigns its iterated logarithm to every positive number, is defined recursively as follows:

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

If 2 is used as the base of the logarithm, the iterated logarithm is also written as . ${\displaystyle \lg ^{*}n}$

Examples

Fig. 1: Example for lg * 4 = 2

Graphically, the determination of the iterated logarithm of a number can be determined by the number of loops that are required according to the example in Fig. 1 to reach the interval [0, 1] on the axis. ${\displaystyle x}$

The iterated logarithm is a very slowly increasing function:

${\displaystyle x}$	${\displaystyle \lg ^{*}x}$
${\displaystyle (-\infty ,1]}$	${\displaystyle 0}$
${\displaystyle (1,2]}$	${\displaystyle 1}$
${\displaystyle (2,4]}$	${\displaystyle 2}$
${\displaystyle (4,16]}$	${\displaystyle 3}$
${\displaystyle (16,65536]}$	${\displaystyle 4}$
${\displaystyle (65536,2^{65536}]}$	${\displaystyle 5}$

use

The iterated logarithm plays a role in estimating the running time for multiplying large integers. The best algorithm to date has an asymptotic running time of

${\displaystyle O\left(n\cdot \log(n)\cdot 2^{3\log ^{*}(n)}\right)}$,

see also Schönhage-Strassen algorithm .

literature

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Algorithmen - An Introduction Oldenburger Wissenschaftsverlag, Munich 2010, ISBN 978-3-486-59002-9 .