Iterierter Logarithmus Inhaltsverzeichnis Definition | Beispiele | Verwendung | Literatur |...
Mathematische Funktion
LogarithmusfunktionMultiplikationSchönhage-Strassen-Algorithmus
Der iterierte Logarithmus einer positiven Zahl n, bezeichnet mit log∗n{displaystyle log ^{*}n} (gesprochen „log Stern von n“), gibt an, wie oft die Logarithmusfunktion anzuwenden ist, damit das Ergebnis kleiner oder gleich 1 ist.
Inhaltsverzeichnis
1 Definition
2 Beispiele
3 Verwendung
4 Literatur
Definition |
Formal ist die Iterierte logarithmische Funktion, die jeder positiven Zahl ihren iterierten Logarithmus zuordnet, wie folgt rekursiv definiert:
- log∗n:={0falls n≤1;1+log∗(logn)falls n>1{displaystyle log ^{*}n:={begin{cases}0&{mbox{falls }}nleq 1;\1+log ^{*}(log n)&{mbox{falls }}n>1end{cases}}}
Wird 2 als Basis des Logarithmus verwendet, schreibt man den iterierten Logarithmus auch als lg∗n{displaystyle lg ^{*}n}.
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 x{displaystyle x}-Achse zu erreichen.
Der iterierte Logarithmus ist eine sehr langsam steigende Funktion:
| x{displaystyle x} | lg∗x{displaystyle lg ^{*}x} |
|---|---|
| (−∞,1]{displaystyle (-infty ,1]} | 0{displaystyle 0} |
| (1,2]{displaystyle (1,2]} | 1{displaystyle 1} |
| (2,4]{displaystyle (2,4]} | 2{displaystyle 2} |
| (4,16]{displaystyle (4,16]} | 3{displaystyle 3} |
| (16,65536]{displaystyle (16,65536]} | 4{displaystyle 4} |
| (65536,265536]{displaystyle (65536,2^{65536}]} | 5{displaystyle 5} |
![(-infty ,1]](https://wikimedia.org/api/rest_v1/media/math/render/svg/cc92152c28209c45f399dd4948ac840d977e1feb)
![(1,2]](https://wikimedia.org/api/rest_v1/media/math/render/svg/1ad6dba240714b52f0e45c8123ebd87a21d4dc52)
![(2,4]](https://wikimedia.org/api/rest_v1/media/math/render/svg/95f52b9b2ea041f44cbbb81e8bd575b236cfaace)
![(4,16]](https://wikimedia.org/api/rest_v1/media/math/render/svg/1bca07cb4a7e6434f8c6e4b328dbcadb08f737c2)
![(16,65536]](https://wikimedia.org/api/rest_v1/media/math/render/svg/9ae550c7aea485ee5aca15f929a06d27f1a60dca)
![(65536,2^{{65536}}]](https://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 bisher beste Algorithmus dafür hat eine asymptotische Laufzeit von
O(n⋅log(n)⋅23log∗(n)){displaystyle Oleft(ncdot log(n)cdot 2^{3log ^{*}(n)}right)},
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.
