Ggthjy

Der iterierte Logarithmus einer positiven Zahl n, bezeichnet mit log∗⁡n{displaystyle log ^{*}n} (gesprochen „log Stern von n“), gibt an, wie oft die Logarithmusfunktion anzuwenden ist, damit das Ergebnis kleiner oder gleich 1 ist.

Definition |

Formal ist die Iterierte logarithmische Funktion, die jeder positiven Zahl ihren iterierten Logarithmus zuordnet, wie folgt rekursiv definiert:

log∗⁡n:={0falls n≤1;1+log∗⁡(log⁡n)falls n>1{displaystyle log ^{*}n:={begin{cases}0&{mbox{falls }}nleq 1;\1+log ^{*}(log n)&{mbox{falls }}n>1end{cases}}}

Wird 2 als Basis des Logarithmus verwendet, schreibt man den iterierten Logarithmus auch als lg∗⁡n{displaystyle lg ^{*}n}.

Beispiele |

Abb. 1: Beispiel für lg* 4 = 2

Graphisch kann die Bestimmung des iterierten Logarithmus einer Zahl bestimmt werden durch die Anzahl der Schleifen, die gemäß dem Beispiel in Abb. 1 benötigt werden, um das Intervall [0, 1] auf der x{displaystyle x}-Achse zu erreichen.

Der iterierte Logarithmus ist eine sehr langsam steigende Funktion:

x{displaystyle x}	lg∗⁡x{displaystyle lg ^{*}x}
(−∞,1]{displaystyle (-infty ,1]}	0{displaystyle 0}
(1,2]{displaystyle (1,2]}	1{displaystyle 1}
(2,4]{displaystyle (2,4]}	2{displaystyle 2}
(4,16]{displaystyle (4,16]}	3{displaystyle 3}
(16,65536]{displaystyle (16,65536]}	4{displaystyle 4}
(65536,265536]{displaystyle (65536,2^{65536}]}	5{displaystyle 5}

Verwendung |

Der iterierte Logarithmus spielt eine Rolle bei der Abschätzung der Laufzeit für die Multiplikation großer ganzer Zahlen. Der bisher beste Algorithmus dafür hat eine asymptotische Laufzeit von

O(n⋅log⁡(n)⋅23log∗⁡(n)){displaystyle Oleft(ncdot log(n)cdot 2^{3log ^{*}(n)}right)},

siehe auch Schönhage-Strassen-Algorithmus.

Literatur |

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Algorithmen – Eine Einführung Oldenburger Wissenschaftsverlag, München 2010, ISBN 978-3-486-59002-9.