Chudnovsky-Algorithmus

aus Wikipedia, der freien Enzyklopädie

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

Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\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[3]; 5 Billionen Stellen von π im August 2010[4]; 10 Billionen Stellen von π im Oktober 2011[5][6]; 12 Billionen Stellen von π im Dezember 2013[7]; 31,4 Billionen Stellen von π im Januar 2019[8]; 50 Billionen Stellen von π im Januar 2020[9][10], über 62,8 Billionen Stellen im August 2021[11] und 100 Billionen im Juni 2022.[12]

Entwicklung

Heegner-Punkte können dabei helfen, sehr schnell konvergente Reihen zu finden, die gegen die Kreiszahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tau = \tfrac{1 + i\sqrt{n}}{2}} mit natürlichen Zahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} , um die Arbeiten von Ramanujan weiterzuführen. Dabei fanden sie eine für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j(\tau) := 1728J(\tau)} und all diese Heegner-Punkte gültige Reihenidentität

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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

beinhaltet.[13] Dabei bezeichnet Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k!} die Fakultät von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} . Daraus konnte nach Einsetzen des Heegner-Punkts Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tau = \tfrac{1 + i\sqrt{163}}{2}} der Chudnovsky-Algorithmus entwickelt werden, mit Hilfe dessen die Kreiszahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi} extrem schnell auf viele Nachkommastellen berechnet werden kann. Er nutzt aus, dass der Wert Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j\left(\tfrac{1 + i\sqrt{163}}{2}\right)} ganzzahlig ist. Über die Methoden, wie man Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j(\tau)} allgemein berechnet, kann man bereits diese und weitere Kuriositäten beobachten. Man weiß wegen der Fourier-Entwicklung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j(\tau) = e^{-2\pi i \tau} + 744 + 196\, 884e^{2\pi i \tau} + \dotsb} , dass für Werte mit größerem Imaginärteil die Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j(\tau)} bereits sehr nahe an Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e^{-2\pi i \tau} + 744} liegt. In der Tat findet man[14]

Ein ausführlicher Beweis dieser Formel findet sich hier:[15]

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

Implementierung des Algorithmus

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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:[16] 

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. ↑ a b c 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 mr:2549375).
  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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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) In: mathworks. 2011, archiviert vom Original am 4. März 2018; abgerufen am 3. März 2018.
Abgerufen von „https://de.wikiup.org/index.php?title=Chudnovsky-Algorithmus&oldid=226387322“