Der Chudnovsky-Algorithmus ist eine von den Chudnovsky-Brüdern im Jahre 1988 entwickelte iterative Methode zur Berechnung beliebig vieler Nachkommastellen der Kreiszahl π. Jede Iteration liefert durchschnittlich 14,81 weitere Dezimalstellen. Der Algorithmus basiert auf der Konvergenz einer verallgemeinerten hypergeometrischen Reihe:

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

Dieser Algorithmus wurde seitdem für alle Weltrekordberechnungen eingesetzt: 2,7 Billionen Stellen von π im Dezember 2009; 5 Billionen Stellen von π im August 2010; 10 Billionen Stellen von π im Oktober 2011; 12 Billionen Stellen von π im Dezember 2013; 31,4 Billionen Stellen von π im Januar 2019; 50 Billionen Stellen von π im Januar 2020, über 62,8 Billionen Stellen im August 2021 und 100 Billionen im Juni 2022.

Entwicklung

Heegner-Punkte können dabei helfen, sehr schnell konvergente Reihen zu finden, die gegen die Kreiszahl ${\displaystyle \pi }$ konvergieren. Vorläufer solcher Reihentypen waren schon von Srinivasa Ramanujan zu Beginn des 20. Jahrhunderts entdeckt worden. Die Brüder David und Gregory Chudnovsky nutzten schließlich die Punkte ${\displaystyle \tau ={\tfrac {1+i{\sqrt {n}}}{2}}}$ mit natürlichen Zahlen ${\displaystyle n}$, um die Arbeiten von Ramanujan weiterzuführen. Dabei fanden sie eine für ${\displaystyle j(\tau ):=1728J(\tau )}$ und all diese Heegner-Punkte gültige Reihenidentität

${\displaystyle \sum _{k=0}^{\infty }\left({\frac {1}{6}}(1-s_{2}(\tau ))+k\right){\frac {(6k)!}{(3k)!k!^{3}}}{\frac {1}{j(\tau )^{k}}}={\frac {\sqrt {-J(\tau )}}{\pi }}{\frac {1}{\sqrt {n(1-J(\tau ))}}},}$

die den durch Eisensteinreihen definierten Term

${\displaystyle s_{2}(\tau )={\frac {E_{4}(\tau )}{E_{6}(\tau )}}\left(E_{2}(\tau )-{\frac {3}{\pi \mathrm {Im} (\tau )}}\right)}$

beinhaltet. Dabei bezeichnet ${\displaystyle k!}$ die Fakultät von ${\displaystyle k}$. Daraus konnte nach Einsetzen des Heegner-Punkts ${\displaystyle \tau ={\tfrac {1+i{\sqrt {163}}}{2}}}$ der Chudnovsky-Algorithmus entwickelt werden, mit Hilfe dessen die Kreiszahl ${\displaystyle \pi }$ extrem schnell auf viele Nachkommastellen berechnet werden kann. Er nutzt aus, dass der Wert ${\displaystyle j\left({\tfrac {1+i{\sqrt {163}}}{2}}\right)}$ ganzzahlig ist. Über die Methoden, wie man ${\displaystyle j(\tau )}$ allgemein berechnet, kann man bereits diese und weitere Kuriositäten beobachten. Man weiß wegen der Fourier-Entwicklung ${\displaystyle j(\tau )=e^{-2\pi i\tau }+744+196\,884e^{2\pi i\tau }+\dotsb }$, dass für Werte ${\displaystyle \tau }$ mit größerem Imaginärteil die Zahl ${\displaystyle j(\tau )}$ bereits sehr nahe an ${\displaystyle e^{-2\pi i\tau }+744}$ liegt. In der Tat findet man

${\displaystyle e^{\pi {\sqrt {163}}}=262\,537\,412\,640\,768\,743{,}\,999\,999\,999\,999\,250\ldots .}$

Ein ausführlicher Beweis dieser Formel findet sich hier:

Diese ist ähnlich der Ramanujan-Formel zur Ermittlung von π, und ist ein Beispiel der Ramanujan-Sato-Reihen.

Implementierung des Algorithmus

${\displaystyle \pi }$ kann mit beliebiger Genauigkeit durch Implementierung des oben genannten Algorithmus in eine dafür geeignete Programmierungsumgebung berechnet werden. Im Folgenden ein Beispiel mit MATLAB:

function P = chud_pi(d)
% CHUD_PI Chudnovsky algorithm for pi.
% chud_pi(d) produces d decimal digits.

k = sym(0);
s = sym(0);
sig = sym(1);
n = ceil(d/14);
for j = 1:n
  s = s + sig * prod(3*k+1:6*k)/prod(1:k)^3 * ...
    (13591409+545140134*k) / 640320^(3*k+3/2);
  k = k+1;
  sig = -sig;
end
S = 1/(12*s);
P = vpa(S,d);

Einzelnachweise

1. ↑ David Chudnovsky, Gregory Chudnovsky: Approximation and complex multiplication according to Ramanujan. In: Ramanujan revisited: proceedings of the centenary conference. 1988. 
2. ↑ FH Graubünden: Algorithmus, Informationen über die Weltrekordberechnung 2021, abgerufen am 26. März 2022
3. 1 2 3 Nayandeep Deka Baruah, Bruce C. Berndt, Heng Huat Chan: Ramanujan’s series for 1/π: a survey. In: American Mathematical Monthly. Band 116, Nr. 7, 2009, S. 567–587, doi:10.4169/193009709X458555, JSTOR:40391165. 
4. ↑ Geeks slice pi to 5 trillion decimal places. Australian Broadcasting Corporation, 6. August 2010, abgerufen am 31. Oktober 2014. 
5. ↑ Alexander Yee, Shigeru Kondo: 10 Trillion Digits of Pi: A Case Study of summing Hypergeometric Series to high precision on Multicore Systems. 2011 (hdl:2142/28348). 
6. ↑ Aron Jacob: Constants clash on pi day. In: New Scientist. 14. März 2012, abgerufen am 31. Oktober 2014. 
7. ↑ Pi - 12.1 Trillion Digits. Abgerufen am 23. August 2021. 
8. ↑ Jens Minor: Neuer Weltrekord: Google Cloud berechnet die Kreiszahl Pi auf 31,4 Billionen Stellen & macht sie frei zugänglich. In: GoogleWatchBlog. 14. März 2019, abgerufen am 14. März 2019 (deutsch). 
9. ↑ Timothy Mullican: Calculating Pi: My attempt at breaking the Pi World Record. 26. Juni 2019, abgerufen am 24. Mai 2020 (amerikanisches Englisch). 
10. ↑ Records set by y-cruncher. Abgerufen am 24. Mai 2020. 
11. ↑ Pi-Challenge - Weltrekordversuch der FH Graubünden - FH Graubünden. Abgerufen am 23. August 2021. 
12. ↑ Emma Haruka Iwao: Even more pi in the sky: Calculating 100 trillion digits of pi on Google Cloud. In: Google Cloud Blog. 8. Juni 2022, abgerufen am 10. Juni 2022 (englisch). 
13. ↑ Nayandeep Deka Baruah, Bruce Berndt, Heng Huat Chan: Ramanujan’s series for ${\displaystyle 1/\pi }$: A survey. Mathematics Student, S. 576.
14. ↑ Jan Hendrik Bruinier, Gerard van der Geer, Günter Harder, Don Zagier: The 1-2-3 of Modular Forms. Lectures at a Summer School in Nordfjordeid, Norway, Springer-Verlag, Berlin/Heidelberg, S. 73.
15. ↑ Lorenz Milla: Ein ausführlicher Beweis der Chudnovsky-Formel mit elementarer Funktionentheorie. 2018, arxiv:1809.00533. 
16. ↑ Cleve Moler: Computing π. (PDF) (Nicht mehr online verfügbar.) In: mathworks. 2011, archiviert vom Original am 4. März 2018; abgerufen am 3. März 2018.