vale - ¿Cuál es la forma más rápida de calcular e a 2 billones de dígitos?
valor de pi completo (2)
Quiero calcular e a 2 billones (2,000,000,000,000) dígitos. Esto es alrededor de 1,8 TiB de pureza e . Acabo de implementar un algoritmo de expansión de la serie taylor utilizando GMP (el código se puede encontrar aquí ).
Desafortunadamente, se bloquea al sumar más de 4000 términos en mi computadora, probablemente porque se queda sin memoria.
¿Cuál es el estado actual de la técnica en computación e ? ¿Qué algoritmo es el más rápido? ¿Alguna implementación de código abierto que valga la pena ver? Por favor, no menciones y cruncher , es de código cerrado.
Como soy el autor del programa y-cruncher que mencionas, agregaré mis 2 centavos.
Para una tarea tan grande, las dos barreras más grandes que deben abordarse son las siguientes:
- Memoria
- Complejidad en tiempo de ejecución
Memoria
2 billones de dígitos es extremo , por decir lo menos. Eso es el doble del récord actual establecido por Shigeru Kondo y yo en 2010 . (Nos tomó más de 9 días para calcular 1 billón de dígitos con y-cruncher.)
En texto plano, eso es alrededor de 1.8 TiB en decimal. En representación binaria empaquetada, eso es 773 GiB.
Si va a hacer aritmética en números de este tamaño, necesitará 773 GiB para cada operando sin contar la memoria virtual.
Hablando de manera factible, y-cruncher en realidad necesita 8.76 TiB de memoria para hacer este cálculo todo en RAM. Por lo tanto, puede esperar que otras implementaciones necesiten el mismo dar o tomar un factor de 2 como máximo.
Dicho esto, dudo que tengas suficiente ram. E incluso si lo hicieras, sería fuertemente NUMA. Así que la alternativa es usar el disco. Pero esto no es trivial, ya que para ser eficiente, debe tratar la memoria como un caché y gestionar todos los datos que se transfieren entre la memoria y el disco.
Complejidad en tiempo de ejecución
Aquí tenemos el otro problema. Para 2 billones de dígitos, necesitarás un algoritmo muy rápido. No cualquier algoritmo rápido, sino un algoritmo de tiempo de ejecución casi lineal.
Tu intento actual se ejecuta en O(N^2) . Entonces, aunque tengas suficiente memoria, no terminará en tu vida.
El enfoque estándar para la computación de alta precisión se ejecuta en O(N log(N)^2) y combina los siguientes algoritmos:
- División binaria en la expansión de la serie de Taylor de
e. - Gran multiplicación basada en FFT
Afortunadamente, GMP ya utiliza una gran multiplicación basada en FFT. Pero le faltan dos características cruciales:
- Cálculo fuera de núcleo (swap) para usar el disco cuando no hay suficiente memoria.
- No está en paralelo.
El segundo punto no es tan importante ya que puedes esperar más tiempo. Pero para todos los propósitos prácticos, es probable que necesites desplegar el tuyo. Y eso es lo que hice cuando escribí y-cruncher.
Dicho esto, hay muchos otros problemas que también deben ser atendidos:
- La división final requerirá un algoritmo rápido como el Método de Newton.
- Si vas a calcular en binario, necesitarás hacer una conversión de radix.
- Si el cálculo llevará mucho tiempo y muchos recursos, es posible que deba implementar una tolerancia a fallos para manejar los fallos de hardware.
Dado que tiene una meta cuántos dígitos desea (2 billones), puede estimar cuántos términos necesitará calcular e para esa cantidad de dígitos. A partir de esto, puede estimar cuántos dígitos adicionales de precisión necesitará realizar un seguimiento para evitar errores de redondeo en el lugar 2 trillón.
Si mi cálculo de la aproximación de Stirling es correcto, el recíproco de 10 a 2 trillones es el recíproco de 100 mil millones de factorial. Entonces eso es aproximadamente cuántos términos necesitarás (100 mil millones). Sin embargo, la historia es un poco mejor que eso, porque comenzarás a poder descartar muchos de los números en el cálculo de los términos mucho antes de eso.
Dado que e se calcula como una suma de factoriales inversos, todos sus términos son racionales y, por lo tanto, son expresables como decimales repetidos. Entonces, la expansión decimal de sus términos será (a) un exponente, (b) una parte no repetitiva y (c) una parte repetitiva. Puede haber algunas eficiencias de las que puede beneficiarse si observa los términos de esta manera.
¡En fin, buena suerte!