[Algorithm] Wie kann ich feststellen, ob meine Pi-Berechnung korrekt ist?


Answers

Zweifellos, für Ihre Zwecke (die ich vermute, ist nur eine Programmierung Übung), ist das Beste daran, Ihre Ergebnisse gegen eine der Listen der Ziffern von Pi im Internet zu überprüfen.

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

Pragmatischer, wenn verschiedene Leute unterschiedliche Algorithmen benutzen, und sie alle zustimmen (eine Zahl wählen), eintausend (Millionen, was auch immer) Dezimalstellen, die Ihnen ein warmes unscharfes Gefühl geben sollten, dass sie es richtig verstanden haben.

Historisch veröffentlichte William Shanks im Jahr 1873 Pi auf 707 Dezimalstellen. Armer Kerl, er hat einen Fehler gemacht, der an der 528. Dezimalstelle beginnt.

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

Schließlich hoffe ich, dass Ihr anfänglicher Algorithmus nicht pi/4 = 1 - 1/3 + 1/5 - 1/7 + ... Das ist vielleicht am einfachsten zu programmieren, aber es ist auch eine der langsamsten Möglichkeiten, dies zu tun . Schauen Sie sich den Wikipedia-Artikel für schnellere Ansätze an.

Question

Ich habe verschiedene Methoden versucht, um ein Programm zu implementieren, das die Ziffern von Pi sequentiell gibt. Ich habe versucht, die Taylor-Serie- Methode, aber es erwies sich als extrem langsam konvergieren (wenn ich mein Ergebnis nach einiger Zeit mit den Online-Werten verglichen). Jedenfalls versuche ich bessere Algorithmen.

Während ich das Programm schrieb, blieb ich bei einem Problem stecken, wie bei allen Algorithmen: Woher weiß ich, dass die n Ziffern, die ich berechnet habe, genau sind?




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

Die Partialsummen der Taylor-Reihe können innerhalb eines Multiplikators des nächsten Terms gezeigt werden, der vom wahren Wert von pi entfernt ist.

Andere Mittel zur Approximation von Pi haben ähnliche Möglichkeiten, den maximalen Fehler zu berechnen.

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