Iterierter Logarithmus

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

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 bisher beste Algorithmus dafür hat eine asymptotische Laufzeit von

,

siehe auch Schönhage-Strassen-Algorithmus.

Literatur

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.