Iterierter Logarithmus

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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.

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 .

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:

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[1] beste bekannte Algorithmus dafür hat eine asymptotische Laufzeit von

,

siehe auch Schönhage-Strassen-Algorithmus.

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. David Harvey, Joris van Der Hoeven: Integer multiplication in time O(n log n). 2019 (hal.science).