Ripetita logaritmo

En matematiko, la ripetita logaritmo de n, skribata kiel log^* n (kutime nomata kiel "log stelo"), estas funkcio de unu argumento. Ĝia valoro estas la kvanto de fojoj je kiuj la logaritma funkcio devas esti ripete aplikita al la argumento por ke la rezulto estu malpli granda ol aŭ egala al 1. La plej simpla formala difino estas ĉi tiu rekursia:

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

aŭ, en pseŭdokodo:

funkcio ripetita_logaritmo(reela n)
    se n ≤ 1
        redoni 0
    alie
        redoni 1 + ripetita_logaritmo(log(n))

Ekvivalenta nerekursia pseŭdokodo:

funkcio ripetita_logaritmo(reela n)
    i = 0
    dum n > 1
        n = log(n)
        i = i + 1
    redoni i

La ripetita logaritmo akceptas ĉiun reelan nombron kaj redonas entjeron.

Por la pozitivaj reelaj nombroj, difino per la kontinua superlogaritmo (retroĵeto de supereksponento) estas ekvivalenta:

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

sed sur la negativaj reelaj nombroj, log^* estas 0, sed $\lceil {\text{slog}}_{e}(-x)\rceil =-1$ por pozitivaj x, tiel la du funkcioj diferenciĝas por negativaj argumentoj.

Figuro 1.
log^*4 = 2

Grafike, ĝi povas esti komprenita kiel la kvanto de zigzagoj bezonataj en la figuro 1 por atingi la intervalon [0, 1] sur la x-akso.

En komputiko, skribo lg^* estas ofte uzita por indiki la duuman ripetitan logaritmon, kiu ripetas la duuman logaritmon anstataŭe.

Ripetita logaritmo estas bone difinita ne nur por bazo 2 kaj bazo e, sed por ĉiu bazo pli granda ol

$e^{1/e}\approx 1.444667$.

La ripetis logaritmo okazas kiel la ordoj de spaca komplikeco (uzata memoro) kaj rula tempo de iuj algoritmoj (vidu ankaŭ en granda O). Ekzemple:

• Trovo de la triangulado de Delaunay de aro de punktoj sciante la eŭklidan minimuman generantan arbon: hazardigita O(n log^* n) tempo, (de Olivier Devillers).
• Algoritmo de Fürer por entjera multipliko: O(n log n 2^{lg* n}) .

La ripetita logaritmo estas ege malrapide kreskanta funkcio, multe pli malrapide ol la logaritmo mem; por ĉiuj praktikaj valoroj de n, ne pli grandaj ol 2⁶⁵⁵³⁶ (kio estas multe pli granda nombro ol la kvanto de partikloj en la universo), eĉ la ripetita logaritmo kun bazo 2 estas ne pli granda ol 5.

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

Pli grandaj bazoj donas pli malgrandan valoron de ripetita logaritmo. La sola funkcio uzata en komplikteorio kiu kreskas pli malrapide estas la inverso de la akermana funkcio.

La ripetita logaritmo estas proksime rilatanta al la ĝeneraligita logaritma funkcio uzata en simetria nivelo-indeksa aritmetiko. Ĝi estas ankaŭ proporcia kun la adicia persisteco de nombro, la kvanto de fojoj je kiu oni devas anstataŭigi la nombron per sumo de ĝiaj ciferoj antaŭ atingi ĝian ripetitan ciferecan sumon.

Vidu ankaŭ

• Superlogaritmo, esence kontinua versio de ĉi tiu funkcio
• Supereksponento, esence la inverso de ĉi tiu funkcio