Logaritmo iterato

In informatica, il logaritmo iterato di n, scritto log* n (solitamente letto "log asterisco"), è il numero di volte che la funzione logaritmo deve essere applicata iterativamente prima che il risultato sia minore o uguale a 1. La più semplice definizione formale è il risultato di questa funzione ricorsiva:

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

Sui numeri reali positivi, il superlogaritmo continuo (tetrazione inversa) è essenzialmente equivalente:

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

ma sui numeri reali negativi, log-asterisco è 0, mentre $\lceil {\text{slog}}_{e}(-x)\rceil =-1$ per x positivi, così le due funzioni differiscono per gli argomenti negativi.

**Figura 1.** Dimostrazione di lg* 4 = 2

In informatica, lg-* si usa spesso per indicare il logaritmo binario iterato, che itera invece il logaritmo binario. Il logaritmo iterato accetta qualsiasi numero reale positivo e produce un intero. Graficamente, può essere inteso come il numero di "zig-zag" richiesti nella Figura 1 per raggiungere l'intervallo [0, 1] sull'asse delle x.

Matematicamente, il logaritmo iterato è ben definito non solo per la base 2 e la base e, ma per qualsiasi base maggiore di $e^{1/e}\approx 1,444667$ .

Analisi degli algoritmi

Il logaritmo iterato è utile nell'analisi degli algoritmi e nella complessità computazionale, apparendo nei limiti della complessità temporale e spaziale di alcuni algoritmi come:

Trovare la triangolazione di Delaunay di un insieme di punti conoscendo l'albero ricoprente minimo euclideo: tempo randomizzato O(n log* n)^[1]
Algoritmo di Fürer per la moltiplicazione degli interi: O(n log n 2^lg* n)
Trovare un massimo approssimato (elemento grande almeno quanto la mediana): lg* n − 4 to lg* n + 2 operazioni parallele^[2]
Algoritmo distribuito per 3-colorare un n-ciclo di Richard Cole e Uzi Vishkin: O(log* n) sessioni di comunicazione sincrona.^[3]^[4]

Il logaritmo iterato cresce a una velocità estremamente lenta, molto più lenta del logaritmo stesso. Per tutti i valori di n rilevanti per il conteggio dei tempi di esecuzione di algoritmi implementati in pratica (cioè, n ≤ 2⁶⁵⁵³⁶, che è di gran lunga maggiore degli atomi dell'universo conosciuto), il logaritmo iterato con base 2 ha un valore non superiore a 5.

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

Le basi superiori danno logaritmi iterati minori. In effetti, la sola funzione comunemente usata nella teoria della complessità che cresce più lentamente è la funzione inversa di Ackermann.

Altre applicazioni

Il logaritmo iterato è strettamente legato alla funzione logaritmica generalizzata usata nell'aritmetica con indici di livello simmetrico. È anche proporzionale alla persistenza additiva di un numero, il numero di volte in cui si deve sostituire il numero con la somma delle sue cifre prima di raggiungere la sua radice numerica.

Santhanam^[5] mostra che DTIME e NTIME sono distinti fino a $n{\sqrt {\log ^{*}n}}.$

Note

^ Olivier Devillers, "Randomization yields simple O(n log* n) algorithms for difficult ω(n) problems.". International Journal of Computational Geometry & Applications 2:01 (1992), pp. 97–111.
^ Noga Alon e Yossi Azar, "Finding an Approximate Maximum". SIAM Journal of Computing 18:2 (1989), pp. 258–267.
^ Richard Cole e Uzi Vishkin: "Deterministic coin tossing with applications to optimal parallel list ranking", Information and Control 70:1(1986), pp. 32–53.
^ * Thomas H. Cormen, Charles A. Leiserson, Ronald L. Rivest e Clifford Stein, Sezione 30.5, in Introduzione agli algoritmi e strutture dati, 1ª ed., MIT Press e McGraw-Hill, 1990, ISBN 0-262-03141-8.
^ On Separators, Segregators and Time versus Space

Bibliografia

Thomas H. Cormen, Charles A. Leiserson, Ronald L. Rivest e Clifford Stein, 3.2: Notazioni standard e funzioni comuni, in Introduzione agli algoritmi e strutture dati, 2ª ed., MIT Press e McGraw-Hill, 2001 [1990], pp. 55–56, ISBN 0-262-03293-7.