Función doble exponencial - Double exponential function
Una función doble exponencial es una constante elevada a la potencia de una función exponencial . La fórmula general es (donde a > 1 yb > 1), que crece mucho más rápidamente que una función exponencial. Por ejemplo, si a = b = 10:
- f (0) = 10
- f (1) = 10 10
- f (2) = 10 100 = googol
- f (3) = 10 1000
- f (100) = 10 10 100 = googolplex .
Los factoriales crecen más rápido que las funciones exponenciales, pero mucho más lento que las funciones doblemente exponenciales. Sin embargo, la tetración y la función de Ackermann crecen más rápidamente. Consulte la notación Big O para una comparación de la tasa de crecimiento de varias funciones.
La inversa de la función exponencial doble es el logaritmo doble ln (ln ( x )).
Secuencias doblemente exponenciales
Una secuencia de números enteros positivos (o números reales) se dice que tiene tasa doblemente exponencial de crecimiento si la función de dar a la n º término de la sucesión está acotada por encima y por debajo por las funciones doblemente exponenciales de n . Ejemplos incluyen
- Los números de Fermat
- Los primos armónicos: Los primos p , en los que la secuencia 1/2 + 1/3 + 1/5 + 1/7 + ⋯ + 1 / p excede 0, 1, 2, 3,…Los primeros números, que comienzan con 0, son 2, 5, 277, 5195977, ... (secuencia A016088 en la OEIS )
- Los números de Double Mersenne
- Los elementos de la secuencia de Sylvester (secuencia A000058 en la OEIS )
- El número de funciones booleanas k -ary :
- Los números primos 2, 11, 1361, ... (secuencia A051254 en la OEIS )
Aho y Sloane observaron que en varias secuencias de números enteros importantes , cada término es una constante más el cuadrado del término anterior. Muestran que tales secuencias se pueden formar redondeando al número entero más cercano los valores de una función doblemente exponencial con exponente medio 2. Ionaşcu y Stănică describen algunas condiciones más generales suficientes para que una secuencia sea el piso de una secuencia doblemente exponencial más una constante. .
Aplicaciones
Complejidad algorítmica
En la teoría de la complejidad computacional , algunos algoritmos toman un tiempo doblemente exponencial:
- Cada procedimiento de decisión para la aritmética de Presburger requiere probablemente al menos un tiempo doblemente exponencial
- Calcular una base de Gröbner sobre un campo. En el peor de los casos, una base de Gröbner puede tener un número de elementos doblemente exponencial en el número de variables. Por otro lado, la complejidad del peor de los casos de los algoritmos de base de Gröbner es doblemente exponencial en el número de variables, así como en el tamaño de la entrada.
- Encontrar un conjunto completo de unificadores asociativo-conmutativos
- Satisfactorio CTL + (que es, de hecho, 2-EXPTIME -completo)
- La eliminación del cuantificador en campos cerrados reales lleva un tiempo doblemente exponencial (ver Descomposición algebraica cilíndrica ).
- Calcular el complemento de una expresión regular
En algunos otros problemas en el diseño y análisis de algoritmos, se utilizan secuencias doblemente exponenciales dentro del diseño de un algoritmo más que en su análisis. Un ejemplo es el algoritmo de Chan para calcular cascos convexos , que realiza una secuencia de cálculos usando valores de prueba h i = 2 2 i (estimaciones para el tamaño de salida eventual), tomando tiempo O ( n log h i ) para cada valor de prueba en la secuencia. . Debido al doble crecimiento exponencial de estos valores de prueba, el tiempo para cada cálculo en la secuencia crece exponencialmente como una función de i , y el tiempo total está dominado por el tiempo para el paso final de la secuencia. Por tanto, el tiempo total del algoritmo es O ( n log h ) donde h es el tamaño de salida real.
Teoría de los números
Algunos límites teóricos de números son doble exponencial. Se sabe que los números perfectos impares con n factores primos distintos son como máximo
resultado de Nielsen (2003). El volumen máximo de un politopo de celosía d con k ≥ 1 puntos de celosía interior es como máximo
un resultado de Pikhurko.
El número primo más grande conocido en la era electrónica ha crecido aproximadamente como una función exponencial doble del año desde que Miller y Wheeler encontraron un número primo de 79 dígitos en EDSAC 1 en 1951.
Biología teórica
En la dinámica de la población, a veces se supone que el crecimiento de la población humana es doble exponencial. Varfolomeyev y Gurevich encajan experimentalmente
donde N ( y ) es la población en millones en el año y .
Física
En el modelo de oscilador de Toda de autopulsación , el logaritmo de amplitud varía exponencialmente con el tiempo (para grandes amplitudes), por lo que la amplitud varía como función doblemente exponencial del tiempo.
Se ha observado que las macromoléculas dendríticas crecen de forma doblemente exponencial.