(Me pregunto si esto es apropiado para las Matemáticas StackExchange o si es mejor en Stack Overflow, ya que se ocupa con la informática, pero me estoy preguntando acerca de la matemática detalles, no sobre los detalles de la programación, por lo que sospecho que aquí es mejor. Pero si se debe poner en otra parte, siéntase libre de moverlo.)
Me preguntaba acerca de esto: el cálculo de $e^{1/e}$ -- lo que yo llamo el "tetrational constante" o "$\eta$" ya que es importante en tetration teoría, a un número muy grande de dígitos, de forma similar a $\pi$ $e$ han sido calculadas. En el caso de $e$, es posible calcular que es bastante eficiente por
$$e = \sum_{n=0}^{\infty} \frac{1}{n!}$$.
Ingenuamente suma de esta serie con simples métodos de la multiplicación de los rendimientos de un tiempo la complejidad de $O(n^2)$ (o tal vez un poco peor si consideramos muy grande $n$ que no caben en un ordenador de la palabra, pero también hay una mejora en el factor debido al hecho de $\frac{1}{n!}$ converge a $0$ un poco más rápido que de manera exponencial: no he trabajado sobre todo este), donde $n$ es el número de dígitos a la informática. Podemos ir mucho más rápido, sin embargo, si aplicamos lo que se llama "división binaria", que cambia el costo de $O(n^2)$ $O(\log(n)\ M(n))$donde $M(n)$ es el costo para multiplicar dos $n$-números de dos dígitos. Utilizando clásicos de grado de la escuela de multiplicación de con $M(n) = O(n^2)$ complejidad no da ninguna ventaja; de hecho, es peor que con $O(n^2 \log(n))$ complejidad en lugar de sólo $O(n^2)$. Pero si aprovechamos el más rápido de la FFT técnica con $M(n) = O(n \log(n))$ (idealizado obligado -- en la práctica nos hemos limitado a la precisión con la que hacer la FFT, y por lo tanto debemos eventualmente pack de menos dígitos por FFT elemento, y, finalmente, tendría que aumentar la precisión de los números utilizados en la FFT.), luego tenemos a $O(n \log(n)^2)$, que es mucho mejor que el enfoque ingenuo.
"Binario división" puede ser generalizada para arbitrario de la serie hipergeométrica. Pero consideremos ahora $e^{1/e}$. Conectar $\frac{1}{e}$ a $\exp$'s de la serie de los rendimientos ingenua de un algoritmo en el que debemos hacer completa la precisión de su trabajo para calcular los términos de la serie -- después de la computación $\frac{1}{e}$! Este algoritmo se ha ligado $O(n\ M(n))$ (o tal vez un poco mejor, debido a las mismas consideraciones de la convergencia de la recíproca factorial como para $e$), lo cual es bastante malo-con clásicos de la multiplicación es (algo mejor, pero peor que $O(n^2)$) $O(n^3)$ e incluso el uso de la FFT de la técnica, todavía es $O(n^2 \log(n))$ -- peor que la computación en la $e$ a través de la pura-enfoque clásico! Tratando de usar el binario de la división no nos salva jack, ya que toda la precisión que se requiere para cada plazo. Podemos tratar de obtener otra serie tomando $f(x) = e^{e^x - 1} - 1$ $x = -1$ a calcular $\frac{e^{1/e}}{e} - 1$
$$\frac{e^{1/e}}{e} - 1 = \sum_{n=1}^{\infty} (-1)^n \frac{B_n}{n!}$$
donde $B_n$ son de la Campana de los números. Esto sólo tiene términos racionales. Pero esta serie es que no hipergeométrica, por lo que el binario de la división de qué no se aplican. Peor aún, converge incluso más lento que el primer enfoque, y dada la falta de una simple recurrencia de sus términos, lo que sugiere que no guarde nada por este método. Así, hay una eficaz fórmula o algoritmo para calcular $e^{1/e}$? Tenga en cuenta que $\pi$ también puede ser calculado por el binario dividir en, digamos, el Chudnovsky fórmula, y por la junta general de accionistas de la iteración (Gauss-Legendre y otros métodos), ambos de los cuales el rendimiento de los algoritmos (cuando FFT multiplicación de los empleados), con las complejidades de la forma $O(n \log(n)^k)$ para algún entero positivo $k$. De modo que la complejidad - $O(n \log(n)^k)$ - es lo que yo tomo como un "eficiente" algoritmo para el propósito de esta pregunta.
