Algoritmo de Chudnovsky

El algoritmo de Chudnovsky es un método rápido para calcular los dígitos de π , basado en las fórmulas de π de Ramanujan . Publicado por los hermanos Chudnovsky en 1988, ^[1] se utilizó para calcular $π$ hasta mil millones de decimales. ^[2]

Se utilizó en los cálculos de récord mundial de 2,7 billones de dígitos de $π$ en diciembre de 2009, ^[3] 10 billones de dígitos en octubre de 2011, ^[4]^[5] 22,4 billones de dígitos en noviembre de 2016, ^[6] 31,4 billones de dígitos en septiembre de 2018-enero de 2019, ^[7] 50 billones de dígitos el 29 de enero de 2020, ^[8] 62,8 billones de dígitos el 14 de agosto de 2021, ^[9] 100 billones de dígitos el 21 de marzo de 2022, ^[10] 105 billones de dígitos el 14 de marzo de 2024, ^[11] y 202 billones de dígitos el 28 de junio de 2024. ^[12]

Algoritmo

El algoritmo se basa en el número de Heegner negado , la función j y en la siguiente serie hipergeométrica generalizada rápidamente convergente : ^[13] Una prueba detallada de esta fórmula se puede encontrar aquí: ^[14] $d=-163$ $j\left({\tfrac {1+i{\sqrt {163}}}{2}}\right)=-640320^{3}$ ${\frac {1}{\pi }}=12\sum _{k=0}^{\infty }{\frac {(-1)^{k}(6k)!(545140134k+13591409)}{(3k)!(k!)^{3}(640320)^{3k+3/2}}}$

Esta identidad es similar a algunas de las fórmulas de Ramanujan que involucran $π$ , ^[13] y es un ejemplo de una serie de Ramanujan-Sato .

La complejidad temporal del algoritmo es . ^[15] $O\left(n(\log n)^{3}\right)$

Optimizaciones

La técnica de optimización utilizada para los cálculos del récord mundial se llama división binaria . ^[16]

División binaria

Se puede sacar un factor de la suma y simplificarlo a ${\textstyle 1/{640320^{3/2}}}$ ${\frac {1}{\pi }}={\frac {1}{426880{\sqrt {10005}}}}\sum _{k=0}^{\infty }{\frac {(-1)^{k}(6k)!(545140134k+13591409)}{(3k)!(k!)^{3}(640320)^{3k}}}$

Sea , y sustituya eso en la suma. $f(n)={\frac {(-1)^{n}(6n)!}{(3n)!(n!)^{3}(640320)^{3n}}}$ ${\frac {1}{\pi }}={\frac {1}{426880{\sqrt {10005}}}}\sum _{k=0}^{\infty }{f(k)\cdot (545140134k+13591409)}$

${\frac {f(n)}{f(n-1)}}$ se puede simplificar a , así que ${\frac {-(6n-1)(2n-1)(6n-5)}{10939058860032000n^{3}}}$ $f(n)=f(n-1)\cdot {\frac {-(6n-1)(2n-1)(6n-5)}{10939058860032000n^{3}}}$

$f(0)=1$ de la definición original de , entonces $f$ $f(n)=\prod _{j=1}^{n}{\frac {-(6j-1)(2j-1)(6j-5)}{10939058860032000j^{3}}}$

Esta definición de no está definida para , así que calcule el primer término de la suma y use la nueva definición de $f$ $n=0$ $f$ ${\frac {1}{\pi }}={\frac {1}{426880{\sqrt {10005}}}}{\Bigg (}13591409+\sum _{k=1}^{\infty }{{\Bigg (}\prod _{j=1}^{k}{\frac {-(6j-1)(2j-1)(6j-5)}{10939058860032000j^{3}}}{\Bigg )}\cdot (545140134k+13591409)}{\Bigg )}$

Sea y , entonces $P(a,b)=\prod _{j=a}^{b-1}{-(6j-1)(2j-1)(6j-5)}$ $Q(a,b)=\prod _{j=a}^{b-1}{10939058860032000j^{3}}$ ${\frac {1}{\pi }}={\frac {1}{426880{\sqrt {10005}}}}{\Bigg (}13591409+\sum _{k=1}^{\infty }{{\frac {P(1,k+1)}{Q(1,k+1)}}\cdot (545140134k+13591409)}{\Bigg )}$

Dejar y $S(a,b)=\sum _{k=a}^{b-1}{{\frac {P(a,k+1)}{Q(a,k+1)}}\cdot (545140134k+13591409)}$ $R(a,b)=Q(a,b)\cdot S(a,b)$ $\pi ={\frac {426880{\sqrt {10005}}}{13591409+S(1,\infty )}}$

$S(1,\infty )$ nunca se puede calcular, por lo tanto, en lugar de calcular y a medida que se aproxima , la aproximación mejorará. $S(1,n)$ $n$ $\infty$ $\pi$ $\pi =\lim _{n\to \infty }{\frac {426880{\sqrt {10005}}}{13591409+S(1,n)}}$

De la definición original de , $R$ $S(a,b)={\frac {R(a,b)}{Q(a,b)}}$ $\pi =\lim _{n\to \infty }{\frac {426880{\sqrt {10005}}\cdot Q(1,n)}{13591409Q(1,n)+R(1,n)}}$

Calcular recursivamente las funciones

Considere un valor tal que $m$ $a<m<b$

$P(a,b)=P(a,m)\cdot P(m,b)$

$Q(a,b)=Q(a,m)\cdot Q(m,b)$
$S(a,b)=S(a,m)+{\frac {P(a,m)}{Q(a,m)}}S(m,b)$
$R(a,b)=Q(m,b)R(a,m)+P(a,m)R(m,b)$

Caso base para la recursión

Considerar $b=a+1$

$P(a,a+1)=-(6a-1)(2a-1)(6a-5)$
$Q(a,a+1)=10939058860032000a^{3}$
$S(a,a+1)={\frac {P(a,a+1)}{Q(a,a+1)}}\cdot (545140134a+13591409)$
$R(a,a+1)=P(a,a+1)\cdot (545140134a+13591409)$

Código Python

#Nota: Para cálculos extremos, se puede usar otro código para ejecutar en una GPU, que es mucho más rápido que esto.importar  decimaldefinición  binaria_split ( a ,  b ): si  b  ==  a  +  1 : Pab  =  - ( 6 * un  -  5 ) * ( 2 * un  -  1 ) * ( 6 * un  -  1 ) Qab  =  10939058860032000  *  a ** 3 Rab  =  Pab  *  ( 545140134 * a  +  13591409 ) demás : m  =  ( a  +  b )  //  2 Pam ,  Qam ,  Ram  =  división binaria ( a ,  m ) Pmb ,  Qmb ,  Rmb  =  división binaria ( m ,  b )  Pab  =  Pam  *  Pmb Qab  =  Qam  *  Qmb Rab  =  Qmb  *  Ram  +  Pam  *  Rmb volver  Pab ,  Qab ,  Rabdefinición  chudnovsky ( n ): """Algoritmo de Chudnovsky.""" P1n ,  Q1n ,  R1n  =  división binaria ( 1 ,  n ) devuelve  ( 426880  *  decimal.decimal ( 10005 ) .sqrt ( ) * Q1n ) / ( 13591409 * Q1n + R1n )      imprimir ( f "1 = { chudnovsky ( 2 ) } " )  # 3.141592653589793238462643384decimal . getcontext () . prec  =  100  # número de dígitos de precisión decimalpara  n  en  el rango ( 2 , 10 ): print ( f " { n } = { chudnovsky ( n ) } " )  # 3.14159265358979323846264338...

Notas

e^{\pi {\sqrt {163}}}\approx 640320^{3}+743.99999999999925\dots

640320^{3}/24=10939058860032000

545140134=163\cdot 127\cdot 19\cdot 11\cdot 7\cdot 3^{2}\cdot 2

13591409=13\cdot 1045493

Véase también

Enlaces externos

[1] ¿Cómo se calcula π en billones de dígitos?

Referencias

^ Chudnovsky, David; Chudnovsky, Gregory (1988), Aproximación y multiplicación compleja según Ramanujan , Ramanujan revisitado: actas de la conferencia del centenario
^ Warsi, Karl; Dangerfield, Jan; Farndon, John; Griffiths, Johny; Jackson, Tom; Patel, Mukul; Pope, Sue; Parker, Matt (2019). El libro de matemáticas: grandes ideas explicadas de forma sencilla . Nueva York: Dorling Kindersley Limited . pág. 65. ISBN. 978-1-4654-8024-8.
^ Baruah, Nayandeep Deka; Berndt, Bruce C.; Chan, Heng Huat (1 de agosto de 2009). "Serie de Ramanujan para 1/π: una encuesta". Mensual Matemático Estadounidense . 116 (7): 567–587. doi :10.4169/193009709X458555.
^ Yee, Alexander; Kondo, Shigeru (2011), 10 billones de dígitos de Pi: un estudio de caso de suma de series hipergeométricas con alta precisión en sistemas multinúcleo , Informe técnico, Departamento de Ciencias de la Computación, Universidad de Illinois, hdl :2142/28348
^ Aron, Jacob (14 de marzo de 2012), "Las constantes chocan en el día de Pi", New Scientist
^ "22,4 billones de dígitos de Pi". www.numberworld.org .
^ "Google Cloud rompe el récord de Pi". www.numberworld.org/ .
^ "El récord Pi regresa al ordenador personal". www.numberworld.org/ .
^ "Pi-Challenge - Weltrekordversuch der FH Graubünden - FH Graubünden". www.fhgr.ch. Consultado el 17 de agosto de 2021 .
^ "Cálculo de 100 billones de dígitos de pi en Google Cloud". cloud.google.com . Consultado el 10 de junio de 2022 .
^ Yee, Alexander J. (14 de marzo de 2024). "Avanzando hacia un nuevo récord de Pi de 105 billones de dígitos". NumberWorld.org . Consultado el 16 de marzo de 2024 .
^ Ranous, Jordan (28 de junio de 2024). "StorageReview Lab rompe el récord mundial de cálculo de Pi con más de 202 billones de dígitos". StorageReview.com . Consultado el 20 de julio de 2024 .
^ ab Baruah, Nayandeep Deka; Berndt, Bruce C.; Chan, Heng Huat (2009), "La serie de Ramanujan para 1/ $π$ : una encuesta", American Mathematical Monthly , 116 (7): 567–587, doi :10.4169/193009709X458555, JSTOR 40391165, MR 2549375
^ Milla, Lorenz (2018), Una prueba detallada de la fórmula de Chudnovsky con medios de análisis complejo básico , arXiv : 1809.00533
^ "y-cruncher - Fórmulas". www.numberworld.org . Consultado el 25 de febrero de 2018 .
^ Brent, Richard P .; Zimmermann, Paul (2010). Aritmética informática moderna . Vol. 18. Cambridge University Press . doi :10.1017/CBO9780511921698. ISBN . 978-0-511-92169-8.