Quelltext der Seite Iterierter Logarithmus

{{Begriffsklärungshinweis|Zur Verwendung des Begriffs in der Wahrscheinlichkeitstheorie siehe [[Gesetz des iterierten Logarithmus]].}}

Der '''iterierte Logarithmus''' einer positiven Zahl ''n'', bezeichnet mit <math>\log^* n</math> (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:

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

Wird 2 als Basis des Logarithmus verwendet, schreibt man den iterierten Logarithmus auch als <math>\lg^* n</math>.

== Beispiele ==
[[Datei:Iterated logarithm.png|300px|mini|'''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 <math>x</math>-Achse zu erreichen.

Der iterierte Logarithmus ist eine sehr langsam steigende Funktion:

{| class="wikitable"
! <math>x</math> !! <math>\lg^* x</math>
|-
| <math>(-\infty, 1]</math> || <math>0</math>
|-
| <math>(1, 2]</math> || <math>1</math>
|-
| <math>(2, 4]</math> || <math>2</math>
|-
| <math>(4, 16]</math> || <math>3</math>
|-
| <math>(16, 65536]</math> || <math>4</math>
|-
| <math>(65536, 2^{65536}]</math> || <math>5</math>
|}

== Verwendung ==

Der iterierte Logarithmus spielt eine Rolle bei der Abschätzung der Laufzeit für die [[Multiplikation]] großer ganzer Zahlen. Der von 2014 bis 2019<ref>David Harvey, [[Joris van der Hoeven|Joris van Der Hoeven]]: ''Integer multiplication in time O(n log n)''. 2019 ([https://hal.science/hal-02070778v1 hal.science]).</ref> beste bekannte Algorithmus dafür hat eine asymptotische Laufzeit von

:<math>O\left(n \cdot \log(n) \cdot 2^{3\log^*(n)}\right)</math>,

siehe auch [[Schönhage-Strassen-Algorithmus]].

== Literatur ==
* {{Literatur
   |Autor=[[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], [[Clifford Stein]]
   |Titel=Algorithmen – Eine Einführung
   |Verlag=Oldenburger Wissenschaftsverlag
   |Ort=München
   |Datum=2010
   |ISBN=978-3-486-59002-9}}

== Einzelnachweise ==
<references />

[[Kategorie:Mathematische Funktion]]
[[Kategorie:Asymptotische Analysis]]