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

Bearbeiten

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

Bearbeiten
 
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

Bearbeiten

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.

Literatur

Bearbeiten

Einzelnachweise

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