Iterierter Logarithmus

Vorlage:Hinweisbaustein

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

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:

<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: Integer multiplication in time O(n log n). 2019 (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

{{#invoke:Vorlage:Literatur|f}}

Einzelnachweise