Wie bestimme ich, ob meine Berechnung von pi korrekt ist?

Ich habe verschiedene Methoden ausprobiert, um ein Programm zu implementieren, das die Ziffern von pi nacheinander angibt. Ich habe die Taylor-Serienmethode ausprobiert , aber sie hat sich als extrem langsam konvergierend erwiesen (als ich mein Ergebnis nach einiger Zeit mit den Online-Werten verglich). Wie auch immer, ich versuche bessere Algorithmen.

Während ich das Programm schrieb, blieb ich wie bei allen Algorithmen bei einem Problem nhängen : Woher weiß ich, dass die von mir berechneten Ziffern korrekt sind?

Da ich der aktuelle Weltrekordhalter für die meisten pi-Ziffern bin, füge ich meine zwei Cent hinzu :

Sofern Sie nicht tatsächlich einen neuen Weltrekord aufstellen, besteht die übliche Praxis darin, die berechneten Ziffern anhand der bekannten Werte zu überprüfen. Das ist also einfach genug.

Tatsächlich habe ich eine Webseite, auf der Ziffernausschnitte aufgelistet sind, um Berechnungen anhand dieser zu überprüfen: http://www.numberworld.org/digits/Pi/

Aber wenn Sie Weltrekord betreten, gibt es nichts zu vergleichen.

In der Vergangenheit besteht der Standardansatz zur Überprüfung der Richtigkeit der berechneten Ziffern darin, die Ziffern mithilfe eines zweiten Algorithmus neu zu berechnen. Wenn also eine der Berechnungen schlecht läuft, stimmen die Ziffern am Ende nicht überein.

Dies ist in der Regel mehr als doppelt so lang wie die benötigte Zeit (da der zweite Algorithmus normalerweise langsamer ist). Dies ist jedoch die einzige Möglichkeit, die berechneten Ziffern zu überprüfen, wenn Sie das Neuland nie zuvor berechneter Ziffern und einen neuen Weltrekord betreten haben.

In den Tagen, als Supercomputer die Rekorde aufstellten, wurden üblicherweise zwei verschiedene AGM-Algorithmen verwendet:

• Gauß-Legendre-Algorithmus
• Borweins Algorithmus

Dies sind beide O(N log(N)^2)Algorithmen, die ziemlich einfach zu implementieren waren.

Heutzutage sieht es jedoch etwas anders aus. In den letzten drei Weltrekorden haben wir anstelle von zwei Berechnungen nur eine Berechnung mit der schnellsten bekannten Formel ( Chudnovsky-Formel ) durchgeführt:

Dieser Algorithmus ist viel schwieriger zu implementieren, aber viel schneller als die AGM-Algorithmen.

Dann überprüfen wir die Binärziffern mit den BBP-Formeln für die Ziffernextraktion .

Mit dieser Formel können Sie beliebige Binärziffern berechnen, ohne alle Ziffern davor zu berechnen . Es wird also verwendet, um die letzten berechneten Binärziffern zu überprüfen. Daher ist es viel schneller als eine vollständige Berechnung.

Der Vorteil davon ist:

1. Es wird nur eine teure Berechnung benötigt.

Der Nachteil ist:

1. Eine Implementierung der Bailey-Borwein-Plouffe (BBP) -Formel ist erforderlich.
2. Ein zusätzlicher Schritt ist erforderlich, um die Radix-Konvertierung von binär nach dezimal zu überprüfen.

_{Ich habe einige Details darüber beschönigt, warum das Überprüfen der letzten Ziffern impliziert, dass alle Ziffern korrekt sind. Dies ist jedoch leicht zu erkennen, da sich jeder Rechenfehler auf die letzten Ziffern ausbreitet.}

Dieser letzte Schritt (Überprüfen der Konvertierung) ist eigentlich ziemlich wichtig. Einer der früheren Weltrekordhalter hat uns tatsächlich darauf hingewiesen, weil ich anfangs nicht ausreichend beschrieben habe, wie es funktioniert.

Also habe ich diesen Ausschnitt aus meinem Blog gezogen:

N = # of decimal digits desired
p = 64-bit prime number

Berechnen Sie A mit der Basis-10-Arithmetik und B mit der Binärarithmetik.

Wenn A = Bdann mit "extrem hoher Wahrscheinlichkeit", ist die Konvertierung korrekt.

Weitere Informationen finden Sie in meinem Blogbeitrag Pi - 5 Billionen Ziffern .

Zweifellos ist es für Ihre Zwecke (von denen ich annehme, dass es sich nur um eine Programmierübung handelt) am besten, Ihre Ergebnisse anhand einer Auflistung der Ziffern von pi im Web zu überprüfen.

Und woher wissen wir, dass diese Werte korrekt sind? Nun, ich könnte sagen, dass es Informatik-Möglichkeiten gibt, um zu beweisen, dass eine Implementierung eines Algorithmus korrekt ist.

Noch pragmatischer: Wenn verschiedene Personen unterschiedliche Algorithmen verwenden und sich alle darauf einigen (eine Zahl auswählen), tausend (Millionen, was auch immer) Dezimalstellen auszuwählen, sollte dies Ihnen ein warmes, verschwommenes Gefühl geben, dass sie es richtig verstanden haben.

Historisch gesehen veröffentlichte William Shanks 1873 pi mit 707 Dezimalstellen. Armer Kerl, er machte einen Fehler, beginnend mit der 528. Dezimalstelle.

Sehr interessanterweise wurde 1995 ein Algorithmus veröffentlicht , der die Eigenschaft hatte, die n-te Ziffer (Basis 16) von pi direkt zu berechnen, ohne alle vorherigen Ziffern berechnen zu müssen !

Schließlich hoffe ich, dass Ihr ursprünglicher Algorithmus nicht pi/4 = 1 - 1/3 + 1/5 - 1/7 + ...so einfach zu programmieren ist, aber es ist auch eine der langsamsten Möglichkeiten, dies zu tun. Weitere Informationen finden Sie im pi-Artikel auf Wikipedia .

Sie können mehrere Ansätze verwenden und prüfen, ob sie zur gleichen Antwort konvergieren. Oder nimm etwas aus dem Netz. Der Chudnovsky-Algorithmus wird normalerweise als sehr schnelle Methode zur Berechnung von pi verwendet. http://www.craig-wood.com/nick/articles/pi-chudnovsky/

Die Taylor-Reihe ist eine Möglichkeit, pi zu approximieren. Wie bereits erwähnt, konvergiert es langsam.

Es kann gezeigt werden, dass die Teilsummen der Taylor-Reihe innerhalb eines Multiplikators des nächsten Terms vom wahren Wert von pi entfernt sind.

Andere Mittel zur Approximation von pi haben ähnliche Methoden zur Berechnung des maximalen Fehlers.

Wir wissen das, weil wir es mathematisch beweisen können.

Sie könnten versuchen, sin(pi/2)(oder cos(pi/2)was auch immer) mit der (ziemlich) schnell konvergierenden Potenzreihe für sin und cos zu rechnen. (Noch besser: Verwenden Sie verschiedene Verdopplungsformeln, um x=0für eine schnellere Konvergenz näher zu rechnen .)

Übrigens ist es besser, als Serien zu verwenden tan(x), wenn man cos(x)beispielsweise als Black Box berechnet (z. B. könnte man Taylor-Serien wie oben verwenden), die Wurzelfindung über Newton durchzuführen. Es gibt sicherlich bessere Algorithmen, aber wenn Sie nicht Tonnen von Ziffern überprüfen möchten, sollte dies ausreichen (und es ist nicht so schwierig zu implementieren, und Sie benötigen nur ein wenig Kalkül, um zu verstehen, warum es funktioniert.)