Der iterierte Logarithmus einer positiven Zahl n, bezeichnet mit (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:

Wird 2 als Basis des Logarithmus verwendet, schreibt man den iterierten Logarithmus auch als .

Beispiele 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 -Achse zu erreichen.

Der iterierte Logarithmus ist eine sehr langsam steigende Funktion:

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 2019David Harvey, Joris van Der Hoeven: Integer multiplication in time O(n log n). 2019 (hal.science). beste bekannte Algorithmus dafür hat eine asymptotische Laufzeit von

,

siehe auch Schönhage-Strassen-Algorithmus.

Literatur

Einzelnachweise

Kategorie:Mathematische Funktion Kategorie:Asymptotische Analysis