Iterierter Logarithmus
From Wikipedia, the free encyclopedia
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
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:
, 
...![{\displaystyle (-\infty ,1]}](http://wikimedia.org/api/rest_v1/media/math/render/svg/cc92152c28209c45f399dd4948ac840d977e1feb)
![{\displaystyle (1,2]}](http://wikimedia.org/api/rest_v1/media/math/render/svg/1ad6dba240714b52f0e45c8123ebd87a21d4dc52)
![{\displaystyle (2,4]}](http://wikimedia.org/api/rest_v1/media/math/render/svg/95f52b9b2ea041f44cbbb81e8bd575b236cfaace)
![{\displaystyle (4,16]}](http://wikimedia.org/api/rest_v1/media/math/render/svg/1bca07cb4a7e6434f8c6e4b328dbcadb08f737c2)
![{\displaystyle (16,65536]}](http://wikimedia.org/api/rest_v1/media/math/render/svg/9ae550c7aea485ee5aca15f929a06d27f1a60dca)
![{\displaystyle (65536,2^{65536}]}](http://wikimedia.org/api/rest_v1/media/math/render/svg/38e7cc9875d59925d82c7a59489411fdd08fdbff)
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[1] beste bekannte Algorithmus dafür hat eine asymptotische Laufzeit von
- ,
siehe auch Schönhage-Strassen-Algorithmus.
Literatur
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Algorithmen – Eine Einführung. Oldenburger Wissenschaftsverlag, München 2010, ISBN 978-3-486-59002-9.