Algorytm Czudnowskiego

Algorytm Czudnowskiego π jest szybką metodą obliczania cyfr liczby π , opartą na wzorach Ramanujana . Została ona opublikowana przez braci Chudnovsky w 1988 roku.

Został użyty w obliczeniach rekordu świata 2,7 biliona cyfr π w grudniu 2009 r., 10 bilionów cyfr w październiku 2011 r., 22,4 biliona cyfr w listopadzie 2016 r., 31,4 biliona cyfr we wrześniu 2018 r. – styczeń 2019 r., 50 bilionów cyfr 29 stycznia 2020 r. , 62,8 bilionów cyfr w dniu 14 sierpnia 2021 r. i 100 bilionów cyfr w dniu 21 marca 2022 r.

Algorytm

Algorytm oparty jest na zanegowanej ${1} +i{\sqrt {163}}}{2}}\right)=-640320^{3}}$$)$ funkcji j ( 1 i na następującym szybko zbieżnym uogólnionym szeregu hipergeometrycznym :

${\ Displaystyle {\ Frac {1} {\ pi}} = 12 \ suma _ {q = 0} ^ {\ infty} {\ Frac {(-1) ^{q}(6q)!(545140134q+13591409)}{(3q)!(q!)^{3}\left(640320\right)^{3q+{\frac {3}{2}}}}} }$

Szczegółowy dowód tego wzoru można znaleźć tutaj:

W przypadku implementacji iteracyjnej o wysokiej wydajności można to uprościć

${\ Displaystyle {\ Frac {(640320) ^ {\ Frac {3} {2}}} {12 \ pi}} = {\ Frac {426880 {\ sqrt {10005} }}{\pi }}=\sum _{q=0}^{\infty}{\frac {(6q)!(545140134q+13591409)}{(3q)!(q!)^{3}\left (-262537412640768000\right)^{q}}}}$

Istnieją 3 duże wyrażenia całkowite (człon wielomianowy M _q , składnik liniowy L _q i składnik wykładniczy X _q ), które tworzą szereg, a π jest równe stałej C podzielonej przez sumę szeregu, jak poniżej:

${\ Displaystyle \ pi = C \ lewo (\ suma _ {q = 0} ^ {\ infty}} {\ Frac {M_ {q} \ cdot L_ {q}} {X_ {q}}} \ prawej) ^ {-1}}$ gdzie:

${\ Displaystyle C = 426880 {\ sqrt {10005}}}$ ,

${\ Displaystyle M_ {q} = {\ Frac {(6q)!} {(3q)! (q!) ^ {3}}}}, L q$ =

$L_ {q} = 545140134q + 13591409}$ ,

${\ Displaystyle X_ {q} = (-262537412640768000) ^ {q}}$ .

Wyrazy M _q , L _q i X _q spełniają następujące rekurencje i można je obliczyć jako takie:

${\ Displaystyle {\ rozpocząć {wyrównane dat} {4} L_ {q + 1} & = L_ {q} + 545140134 \, \, & & {\ textrm {gdzie}}\,\,L_{0}&&=13591409\\[4pt]X_{q+1}&=X_{q}\cdot (-262537412640768000)&&{\textrm {gdzie}}\,\ ,X_{0}&&=1\\[4pt]M_{q+1}&=M_{q}\cdot \left({\frac {(12q+2)(12q+6)(12q+10)} {(q+1)^{3}}}\right)\,\,&&{\textrm {gdzie}}\,\,M_{0}&&=1\\[4pt]\end{wyrównanydat}}}$

Obliczenie M _q można dodatkowo zoptymalizować, wprowadzając dodatkowy składnik K _q w następujący sposób:

${\ Displaystyle {\ rozpocząć{wyrównanedat}{4}K_{q+1}&=K_{q}+12\,\,&&{\textrm {gdzie}}\,\,K_{0}&&=-6\\[4pkt] M_{q+1}&=M_{q}\cdot \left({\frac {K_{q+1}^{3}-16K_{q+1}}{\left(q+1\right)^ {3}}}\right)\,\,&&{\textrm {gdzie}}\,\,M_{0}&&=1\\[12pt]\end{alignedat}}}$

Zauważ to

$_$ {

$_ = 262537412640768000}$

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

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

Ta tożsamość jest podobna do niektórych formuł Ramanujana obejmujących π i jest przykładem szeregu Ramanujana – Sato .

Złożoność czasowa algorytmu wynosi ${\ Displaystyle O \ lewo (n (\ log n) ^ {3} \ prawej)}$ .

Zobacz też

• Algorytm Borweina
• Numeryczne przybliżenia π
• szereg Ramanujana-Sato