Logaritmo iterado

Función inversa de una torre de potencias

En informática , el logaritmo iterado de , escrito log* (normalmente se lee " log star "), es el número de veces que se debe aplicar iterativamente la función logaritmo antes de que el resultado sea menor o igual a . ^[1] La definición formal más simple es el resultado de esta relación de recurrencia : ${\estilo de visualización n}$ ${\estilo de visualización n}$ ${\estilo de visualización 1}$

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

En informática, lg * se utiliza a menudo para indicar el logaritmo iterado binario , que itera el logaritmo binario (con base ) en lugar del logaritmo natural (con base e ). Matemáticamente, el logaritmo iterado está bien definido para cualquier base mayor que , no solo para base y base e . La función "superlogaritmo" es "esencialmente equivalente" al logaritmo iterado de base (aunque difiere en detalles menores de redondeo ) y forma una inversa a la operación de tetración . ^[2] ${\estilo de visualización 2}$ $e^{1/e}\aproximadamente 1,444667$ ${\estilo de visualización 2}$ $\mathrm {slog} _ {b}(n)$ ${\estilo de visualización b}$

Análisis de algoritmos

El logaritmo iterado es útil en el análisis de algoritmos y complejidad computacional , apareciendo en los límites de complejidad temporal y espacial de algunos algoritmos como:

Encontrar la triangulación de Delaunay de un conjunto de puntos conociendo el árbol de expansión mínimo euclidiano : tiempo aleatorio O ( n log* n ). ^[3]
Algoritmo de Fürer para la multiplicación de números enteros: O( n log n 2 ^{O (lg* n )} ).
Encontrar un máximo aproximado (elemento al menos tan grande como la mediana): lg* n − 1 ± 3 operaciones paralelas. ^[4]
Algoritmo distribuido de Richard Cole y Uzi Vishkin para colorear 3 veces un ciclo n : O (log* n ) rondas de comunicación sincrónica. ^[5]

El logaritmo iterado crece a un ritmo extremadamente lento, mucho más lento que el logaritmo mismo o sus repeticiones. Esto se debe a que la tetración crece mucho más rápido que la exponencial iterada:

${^{y}b}=\underbrace {b^{b^{\cdot ^{\cdot ^{b}}}}} _{y}\gg \underbrace {b^{b^{\cdot ^{\cdot ^{b^{y}}}}}} _{n}$

La inversa crece mucho más lento: . $Estilo de visualización: log _{b}^{*}x\ll log _{b}^{n}x}$

Para todos los valores de n relevantes para contar los tiempos de ejecución de los algoritmos implementados en la práctica (es decir, n ≤ 2 ⁶⁵⁵³⁶ , que es mucho más que el número estimado de átomos en el universo conocido), el logaritmo iterado con base 2 tiene un valor no mayor que 5.

El logaritmo iterado en base 2
incógnita	lg * x
$(-\infty, 1]$	0
$(1, 2]$	1
$(2, 4]$	2
$(4, 16]$	3
$(16, 65536]$	4
$(65536, 2 65536]$	5

Las bases más altas dan logaritmos iterados más pequeños.

Otras aplicaciones

El logaritmo iterado está estrechamente relacionado con la función logaritmo generalizado que se utiliza en la aritmética de índice de nivel simétrico . La persistencia aditiva de un número , la cantidad de veces que alguien debe reemplazar el número por la suma de sus dígitos antes de llegar a su raíz digital , es . $O(\log ^{*}n)$

En la teoría de la complejidad computacional , Santhanam ^[6] muestra que los recursos computacionales DTIME ( tiempo de cálculo para una máquina de Turing determinista ) y NTIME (tiempo de cálculo para una máquina de Turing no determinista ) son distintos hasta $n{\sqrt {\log ^{*}n}}.$

Véase también

Función de Ackermann inversa , una función de crecimiento aún más lento que también se utiliza en la teoría de la complejidad computacional.

Referencias

^ Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2009) [1990]. "La función logaritmo iterado, en la Sección 3.2: Notaciones estándar y funciones comunes". Introducción a los algoritmos (3.ª ed.). MIT Press y McGraw-Hill. págs. 58–59. ISBN 0-262-03384-4.
^ Furuya, Isamu; Kida, Takuya (2019). "Compactación de numerales de la Iglesia". Algoritmos . 12 (8) 159: 159. doi : 10.3390/a12080159 . MR 3998658.
^ Devillers, Olivier (marzo de 1992). "La aleatorización produce algoritmos O ( n log ∗ ⁡ n ) {\displaystyle O(n\log ^{\ast }n)} simples para problemas Ω ( n ) {\displaystyle \Omega (n)} difíciles" (PDF) . Revista internacional de geometría computacional y aplicaciones . 2 (1): 97–111. arXiv : cs/9810007 . doi :10.1142/S021819599200007X. MR 1159844. S2CID 60203.
^ Alon, Noga ; Azar, Yossi (abril de 1989). "Encontrar un máximo aproximado" (PDF) . SIAM Journal on Computing . 18 (2): 258–267. doi :10.1137/0218017. MR 0986665.
^ Cole, Richard ; Vishkin, Uzi (julio de 1986). "Lanzamiento de moneda determinista con aplicaciones a la clasificación óptima de listas paralelas" (PDF) . Información y Control . 70 (1): 32–53. doi : 10.1016/S0019-9958(86)80023-7 . MR 0853994.
^ Santhanam, Rahul (2001). "Sobre separadores, segregadores y tiempo versus espacio" (PDF) . Actas de la 16.ª Conferencia Anual del IEEE sobre Complejidad Computacional, Chicago, Illinois, EE. UU., 18-21 de junio de 2001. IEEE Computer Society . págs. 286–294. doi :10.1109/CCC.2001.933895. ISBN . 0-7695-1053-1.

[1] Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2009) [1990]. "La función logaritmo iterado, en la Sección 3.2: Notaciones estándar y funciones comunes". Introducción a los algoritmos (3.ª ed.). MIT Press y McGraw-Hill. págs. 58–59. ISBN 0-262-03384-4.

[2] Furuya, Isamu; Kida, Takuya (2019). "Compactación de numerales de la Iglesia". Algoritmos . 12 (8) 159: 159. doi : 10.3390/a12080159 . MR 3998658.

[3] Devillers, Olivier (marzo de 1992). "La aleatorización produce algoritmos O ( n log ∗ ⁡ n ) {\displaystyle O(n\log ^{\ast }n)} simples para problemas Ω ( n ) {\displaystyle \Omega (n)} difíciles" (PDF) . Revista internacional de geometría computacional y aplicaciones . 2 (1): 97–111. arXiv : cs/9810007 . doi :10.1142/S021819599200007X. MR 1159844. S2CID 60203.

[4] Alon, Noga ; Azar, Yossi (abril de 1989). "Encontrar un máximo aproximado" (PDF) . SIAM Journal on Computing . 18 (2): 258–267. doi :10.1137/0218017. MR 0986665.

[5] Cole, Richard ; Vishkin, Uzi (julio de 1986). "Lanzamiento de moneda determinista con aplicaciones a la clasificación óptima de listas paralelas" (PDF) . Información y Control . 70 (1): 32–53. doi : 10.1016/S0019-9958(86)80023-7 . MR 0853994.

[6] Santhanam, Rahul (2001). "Sobre separadores, segregadores y tiempo versus espacio" (PDF) . Actas de la 16.ª Conferencia Anual del IEEE sobre Complejidad Computacional, Chicago, Illinois, EE. UU., 18-21 de junio de 2001. IEEE Computer Society . págs. 286–294. doi :10.1109/CCC.2001.933895. ISBN . 0-7695-1053-1.