Itererad logaritm

För satsen i sannolikhetsteorin, se Lagen för den itererade logaritmen .

  Inom datavetenskap är den itererade logaritmen av $n$ , skriven logg * $n$ (vanligtvis läs " log star "), antalet gånger logaritmfunktionen måste tillämpas iterativt innan resultatet blir mindre än eller lika med $1$ . Den enklaste formella definitionen är resultatet av denna återkommande relation :

$\log ^{*}n:={\begin{cases}0&{\mbox{if }}n\leq 1;\\1+\ log ^{*}(\log n)&{\mbox{if }}n>1\end{cases}}$

På de positiva reella talen är den kontinuerliga superlogaritmen (invers tetration ) i huvudsak ekvivalent:

$\log ^{*}n=\lceil \mathrm {slog} _{e}(n)\rceil$

dvs basen b itererad logaritmen är $\log ^{*}n=y$ om n ligger inom intervallet $^{y-1} b<n\leq \ ^{y}b$ , där ${^{y}b}=\underbrace {b^{b^{\cdot ^{\cdot ^{b}}}}} _{y}$ betecknar tetration. Men på de negativa reella talen är log-star $0$ , medan $\lceil {\text{slog}}_{e}(-x) \rceil =-1$ för positiv $x$ , så de två funktionerna skiljer sig åt för negativa argument.

Figur 1. Visar log* 4 = 2 för den bas-e itererade logaritmen. Värdet på den itererade logaritmen kan hittas genom att "sick-zagga" på kurvan y = log _b (x) från ingången n, till intervallet [0,1]. I detta fall är b = e. Sicksackningen innebär att man börjar från punkten (n, 0) och iterativt flyttas till (n, log _b (n) ), till (0, log _b (n) ), till (log _b (n), 0 ).

Den itererade logaritmen accepterar alla positiva reella tal och ger ett heltal . Grafiskt kan det förstås som antalet "sick-zagg" som behövs i figur 1 för att nå intervallet $\displaystyle [0,1]}$ på x -axeln.

Inom datavetenskap används lg * ofta för att indikera den binära itererade logaritmen , som itererar den binära logaritmen (med bas $2$ ) istället för den naturliga logaritmen (med bas e ).

Matematiskt är den itererade logaritmen väldefinierad för alla baser större än ${\displaystyle e^{1/e}\approx 1,444667} ,$ inte bara för bas $2$ och bas e .

Analys av algoritmer

Den itererade logaritmen är användbar vid analys av algoritmer och beräkningskomplexitet , som förekommer i tids- och rymdkomplexitetsgränserna för vissa algoritmer som:

•    Att hitta Delaunay-trianguleringen av en uppsättning punkter med kännedom om det euklidiska minimumspännande trädet : randomiserad O ( n log * n ) tid.
• Fürers algoritm för heltalsmultiplikation: O( n log n 2   ^{O (lg * n )} ).
•    Hitta ett ungefärligt maximum (element minst lika stort som medianen): lg * n − 4 till lg * n + 2 parallella operationer.
•   Richard Cole och Uzi Vishkins distribuerade algoritm för 3-färgning av en n -cykel : O ( log * n ) synkrona kommunikationsrundor.

Den itererade logaritmen växer i extremt långsam takt, mycket långsammare än själva logaritmen. För alla värden på n som är relevanta för att räkna körtiderna för algoritmer implementerade i praktiken (dvs. n ≤ 2 ⁶⁵⁵³⁶ , vilket är mycket mer än det uppskattade antalet atomer i det kända universum), har den itererade logaritmen med bas 2 ett värde no mer än 5.

Bas-2 itererade logaritmen

x	lg * x
(−∞, 1]	0
(1, 2]	1
(2, 4]	2
(4, 16]	3
(16, 65536]	4
(65536, 2 65536 ]	5

Högre baser ger mindre itererade logaritmer. Faktum är att den enda funktionen som vanligtvis används i komplexitetsteorin som växer långsammare är den omvända Ackermann-funktionen .

Andra applikationer

Den itererade logaritmen är nära relaterad till den generaliserade logaritmfunktionen som används i symmetrisk nivåindexaritmetik . Den additiva persistensen av ett tal , antalet gånger någon måste ersätta talet med summan av dess siffror innan det når dess digitala rot , är $O(\log ^{*}n)$ .

I beräkningskomplexitetsteori visar Santhanam att beräkningsresurserna DTIME — beräkningstid för en deterministisk Turingmaskin — och NTIME — beräkningstid för en icke-deterministisk Turingmaskin — är distinkta upp till $n{\sqrt {\log ^{*}n}}.$