Algoritmo de Chudnovsky

Método rápido para calcular los dígitos de π

El algoritmo de Chudnovsky es un método rápido para calcular los dígitos de π , basado en las fórmulas π de Ramanujan . Fue publicado por los hermanos Chudnovsky en 1988. ^[1]

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

Algoritmo

El algoritmo se basa en el número de Heegner negado , la función j y en las siguientes series hipergeométricas generalizadas rápidamente convergentes : ^[2] ${\displaystyle d=-163}$ ${\displaystyle j\left({\tfrac {1+i{\sqrt {163}}}{2}}\right)=-640320^{3}}$

$${\displaystyle {\frac {1}{\pi }}=12\sum _{k=0}^{\infty }{\frac {(-1)^{k}(6k)!(545140134k+13591409)}{(3k)!(k!)^{3}(640320)^{3k+3/2}}}}$$

^[10]

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

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

Optimizaciones

La técnica de optimización utilizada para los cálculos de récords mundiales se llama división binaria . ^[12]

división binaria

Se puede sacar un factor de la suma y simplificarlo a ${\textstyle 1/{640320^{3/2}}}$

$${\displaystyle {\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 sustitúyalo en la suma. ${\displaystyle f(n)={\frac {(-1)^{n}(6n)!}{(3n)!(n!)^{3}(640320)^{3n}}}}$

$${\displaystyle {\frac {1}{\pi }}={\frac {1}{426880{\sqrt {10005}}}}\sum _{k=0}^{\infty }{f(k)\cdot (545140134k+13591409)}}$$

${\displaystyle {\frac {f(n)}{f(n-1)}}}$se puede simplificar a , entonces ${\displaystyle {\frac {-(6n-1)(2n-1)(6n-5)}{10939058860032000n^{3}}}}$

$${\displaystyle f(n)=f(n-1)\cdot {\frac {-(6n-1)(2n-1)(6n-5)}{10939058860032000n^{3}}}}$$

${\displaystyle f(0)=1}$de la definición original de , entonces ${\displaystyle f}$

$${\displaystyle 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 ${\displaystyle f}$ ${\displaystyle n=0}$ ${\displaystyle f}$

$${\displaystyle {\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 )}}$$

Deja y , entonces ${\displaystyle P(a,b)=\prod _{j=a}^{b-1}{-(6j-1)(2j-1)(6j-5)}}$ ${\displaystyle Q(a,b)=\prod _{j=a}^{b-1}{10939058860032000j^{3}}}$

$${\displaystyle {\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 ${\displaystyle S(a,b)=\sum _{k=a}^{b-1}{{\frac {P(a,k+1)}{Q(a,k+1)}}\cdot (545140134k+13591409)}}$ ${\displaystyle R(a,b)=Q(a,b)\cdot S(a,b)}$

$${\displaystyle \pi ={\frac {426880{\sqrt {10005}}}{13591409+S(1,\infty )}}}$$

${\displaystyle S(1,\infty )}$nunca se puede calcular, por lo que, en su lugar, calcule y a medida que se acerque , la aproximación mejorará. ${\displaystyle S(1,n)}$ ${\displaystyle n}$ ${\displaystyle \infty }$ ${\displaystyle \pi }$

$${\displaystyle \pi \approx {\frac {426880{\sqrt {10005}}}{13591409+S(1,n)}}}$$

De la definición original de , ${\displaystyle R}$ ${\displaystyle S(a,b)={\frac {R(a,b)}{Q(a,b)}}}$

$${\displaystyle \pi \approx {\frac {426880{\sqrt {10005}}\cdot Q(1,n)}{13591409Q(1,n)+R(1,n)}}}$$

Calcular recursivamente las funciones.

Considere un valor tal que ${\displaystyle m}$ ${\displaystyle a<m<b}$

• ${\displaystyle P(a,b)=P(a,m)\cdot P(m,b)}$

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

Caso base para la recursividad

Considerar ${\displaystyle b=a+1}$

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

código pitón

importar  decimalesdef  división_binaria ( 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 : metro  =  ( a  +  b )  //  2 Pam ,  Qam ,  Ram  =  binario_split ( a ,  m ) Pmb ,  Qmb ,  Rmb  =  división_binaria ( m ,  b )  Pab  =  Pam  *  Pmb Qab  =  Qam  *  Qmb Rab  =  Qmb  *  Ram  +  Pam  *  Rmb volver  Pab ,  Qab ,  Rabdef  chudnovsky ( n ): """Algoritmo de Chudnovsky.""" P1n ,  Q1n ,  R1n  =  división_binaria ( 1 ,  n ) retorno  ( 426880  *  decimal . Decimal ( 10005 ) . sqrt ()  *  Q1n )  /  ( 13591409 * Q1n  +  R1n )imprimir ( chudnovsky ( 2 ))  # 3.141592653589793238462643384decimales . obtener contexto () . prec  =  100para  n  en el  rango ( 2 , 10 ): print ( f " { n =} { chudnovsky ( n ) } " ) # 3.14159265358979323846264338...  

Notas

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

${\displaystyle 640320^{3}/24=10939058860032000}$

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

${\displaystyle 13591409=13\cdot 1045493}$

Ver también

• Serie Ramanujan-Sato
• Fórmula Bailey-Borwein-Plouffe
• algoritmo de Borwein
• Aproximaciones de π

Referencias

1. Chudnovsky, David; Chudnovsky, Gregory (1988), Aproximación y multiplicación compleja según Ramanujan , Ramanujan revisitado: actas de la conferencia del centenario
2. 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
3. Sí, Alejandro; Kondo, Shigeru (2011), 10 billones de dígitos de Pi: un estudio de caso sobre la 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
4. Aron, Jacob (14 de marzo de 2012), "Las constantes chocan el día pi", New Scientist
5. "22,4 billones de dígitos de Pi". www.numberworld.org .
6. "Google Cloud derriba el récord Pi". www.numberworld.org/ .
7. "El registro Pi regresa a la computadora personal". www.numberworld.org/ .
8. "Pi-Challenge - Weltrekordversuch der FH Graubünden - FH Graubünden". www.fhgr.ch.​ Consultado el 17 de agosto de 2021 .
9. "Cálculo de 100 billones de dígitos de pi en Google Cloud". nube.google.com . Consultado el 10 de junio de 2022 .
10. Milla, Lorenz (2018), Una prueba detallada de la fórmula de Chudnovsky con medios de análisis complejo básico , arXiv : 1809.00533
11. "y-cruncher - Fórmulas". www.numberworld.org . Consultado el 25 de febrero de 2018 .
12. Rayton, Joshua (septiembre de 2023), ¿Cómo se calcula π en billones de dígitos?, YouTube