www.wikidata.de-de.nina.az

Iterierter Logarithmus Der Titel dieses Artikels ist mehrdeutig Zur Verwendung des Begriffs in der Wahrscheinlichkeitsth

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 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 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).
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Der Titel dieses Artikels ist mehrdeutig Zur Verwendung des Begriffs in der Wahrscheinlichkeitstheorie siehe Gesetz des iterierten Logarithmus 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 5 EinzelnachweiseDefinition BearbeitenFormal ist die Iterierte logarithmische Funktion die jeder positiven Zahl ihren iterierten Logarithmus zuordnet wie folgt rekursiv definiert log n 0falls n 1 1 log log n falls n gt 1 displaystyle log n begin cases 0 amp mbox falls n leq 1 1 log log n amp mbox falls n gt 1 end cases nbsp Wird 2 als Basis des Logarithmus verwendet schreibt man den iterierten Logarithmus auch als lg n displaystyle lg n nbsp Beispiele Bearbeiten nbsp Abb 1 Beispiel fur lg 4 2Graphisch kann die Bestimmung des iterierten Logarithmus einer Zahl bestimmt werden durch die Anzahl der Schleifen die gemass dem Beispiel in Abb 1 benotigt werden um das Intervall 0 1 auf der x displaystyle x nbsp Achse zu erreichen Der iterierte Logarithmus ist eine sehr langsam steigende Funktion x displaystyle x nbsp lg x displaystyle lg x nbsp 1 displaystyle infty 1 nbsp 0 displaystyle 0 nbsp 1 2 displaystyle 1 2 nbsp 1 displaystyle 1 nbsp 2 4 displaystyle 2 4 nbsp 2 displaystyle 2 nbsp 4 16 displaystyle 4 16 nbsp 3 displaystyle 3 nbsp 16 65536 displaystyle 16 65536 nbsp 4 displaystyle 4 nbsp 65536 265536 displaystyle 65536 2 65536 nbsp 5 displaystyle 5 nbsp Verwendung BearbeitenDer iterierte Logarithmus spielt eine Rolle bei der Abschatzung der Laufzeit fur die Multiplikation grosser ganzer Zahlen Der von 2014 bis 2019 1 beste bekannte Algorithmus dafur hat eine asymptotische Laufzeit von O n log n 23log n displaystyle O left n cdot log n cdot 2 3 log n right nbsp siehe auch Schonhage Strassen Algorithmus Literatur BearbeitenThomas H Cormen Charles E Leiserson Ronald L Rivest Clifford Stein Algorithmen Eine Einfuhrung Oldenburger Wissenschaftsverlag Munchen 2010 ISBN 978 3 486 59002 9 Einzelnachweise Bearbeiten David Harvey Joris van Der Hoeven Integer multiplication in time O n log n 2019 hal science Abgerufen von https de wikipedia org w index php title Iterierter Logarithmus amp oldid 233624525