Erforderliche Arbeitsgenauigkeit für den BBP-Algorithmus?

Question

Ich möchte das berechnen NZiffer von Pi in einer Umgebung mit wenig Speicher.Da mir keine Dezimalzahlen zur Verfügung stehen, hier Nur ganzzahliger BBP-Algorithmus in Python war ein toller Ausgangspunkt.Ich muss jeweils nur eine Ziffer von Pi berechnen. Wie kann ich den niedrigsten Wert ermitteln, den ich einstellen kann, d. h. die „Anzahl der Stellen der Arbeitsgenauigkeit“?

D=4 gibt mir viele richtige Ziffern, aber ein paar Ziffern sind um eins daneben.Wenn ich beispielsweise die Ziffer 393 mit einer Genauigkeit von 4 berechne, erhalte ich 0xafda, aus dem ich die Ziffer 0xa extrahiere.Die korrekte Ziffer ist jedoch 0xb.

Unabhängig davon, wie hoch ich D einsetze, scheint das Testen einer ausreichenden Anzahl von Ziffern eine Eins zu finden, bei der die Formel einen falschen Wert zurückgibt.

Ich habe versucht, die Genauigkeit zu erhöhen, wenn die Ziffer „nahe“ an einer anderen liegt, z. B.0x3fff oder 0x1000, kann aber keine gute Definition von „close“ finden;Wenn ich zum Beispiel bei Ziffer 9798 rechne, erhalte ich 0xCde6 , was nicht sehr nahe an 0xd000 liegt, aber die richtige Ziffer ist 0xd.

Kann mir jemand helfen, herauszufinden, wie viel Arbeitsgenauigkeit erforderlich ist, um eine bestimmte Ziffer mit diesem Algorithmus zu berechnen?

Danke schön,

bearbeiten
Als Referenz:

precision (D)   first wrong digit
-------------   ------------------
3               27
4               161
5               733
6               4329
7               21139
8+              ???

Beachten Sie, dass ich jeweils eine Ziffer berechne, z. B.:

for i in range(1,n):
    D = 3 # or whatever precision I'm testing
    digit = pi(i) # extracts most significant digit from integer-only BBP result
    if( digit != HARDCODED_PI[i] ):
        print("non matching digit #%d, got %x instead of %x" % (i,digit,HARDCODED_PI[i]) )

Answer 1

Egal wie hoch ich D setze, es scheint dass die Prüfung einer ausreichenden Anzahl von digits findet eine, bei der die Formel gibt einen falschen Wert zurück.

Sie erhalten immer eine Fehlermeldung, wenn Sie eine ausreichende Anzahl von Ziffern testen. Der Algorithmus verwendet keine willkürliche Genauigkeit, sodass irgendwann Rundungsfehler auftreten.

Die unbegrenzte Iteration mit Pause, wenn sich die Ziffer nicht ändert, wird schwierig sein, die für eine bestimmte Anzahl von Ziffern erforderliche Mindestgenauigkeit zu bestimmen.

Am besten bestimmen Sie es empirisch, idealerweise durch Vergleich mit einer bekanntermaßen korrekten Quelle, und erhöhen Sie die Genauigkeit der Stellenanzahl, bis Sie eine Übereinstimmung erhalten. Wenn keine korrekte Quelle verfügbar ist, beginnen Sie mit Ihrer maximalen Genauigkeit (die meiner Meinung nach 14 beträgt). , da die 15. Ziffer fast immer einen Rundungsfehler enthält.)

BEARBEITEN:Genauer gesagt enthält der Algorithmus eine Schleife – von 0 bis n, wobei n die zu berechnende Ziffer ist.Jede Iteration der Schleife führt zu einer bestimmten Fehlermenge.Nach einer ausreichenden Anzahl von Schleifendurchläufen wird sich der Fehler auf die höchstwertige Ziffer auswirken, die Sie berechnen, und das Ergebnis ist daher falsch.

Der Wikipedia-Artikel verwendet eine Genauigkeit von 14 Ziffern, was ausreicht, um die 10**8 Ziffer korrekt zu berechnen.Wie Sie gezeigt haben, führen weniger Ziffern an Genauigkeit dazu, dass Fehler früher auftreten, da die Genauigkeit geringer ist und Fehler bei weniger Iterationen sichtbar werden.Das Nettoergebnis ist, dass der Wert für n, für den wir eine Ziffer korrekt berechnen können, mit weniger Zifferngenauigkeit kleiner wird.

Wenn Sie eine Genauigkeit von D Hexadezimalstellen haben, sind das D*4 Bits.Bei jeder Iteration wird im niedrigstwertigen Bit ein Fehler von 0,5 Bit eingeführt, sodass bei zwei Iterationen die Möglichkeit besteht, dass das LSB falsch ist.Bei der Summierung werden diese Fehler addiert und somit akkumuliert.Wenn die Anzahl der summierten Fehler das LSB in der höchstwertigen Ziffer erreicht, ist die einzelne Ziffer, die Sie extrahieren, falsch.Grob gesagt ist dies der Fall, wenn N > 2**(D-0,75).(Korrigiert auf einer logarithmischen Basis.)

Wenn Sie Ihre Daten empirisch extrapolieren, scheint die ungefähre Übereinstimmung N=~(2**(2,05*D)) zu sein, obwohl es nur wenige Datenpunkte gibt, sodass dies möglicherweise kein genauer Prädiktor ist.

Der von Ihnen gewählte BBP-Algorithmus ist iterativ und daher dauert die Berechnung der Ziffern in der Sequenz zunehmend länger.Um die Ziffern 0..n zu berechnen, benötigen Sie O(n^2) Schritte.

Der Wikipedia-Artikel enthält eine Formel zur Berechnung der n-ten Ziffer, die keine Iteration, sondern nur Potenzierung und rationale Zahlen erfordert.Dies erleidet nicht den gleichen Präzisionsverlust wie der iterative Algorithmus und Sie können jede Ziffer von Pi nach Bedarf in konstanter Zeit (oder im schlimmsten Fall logarithmischen Typs, abhängig von der Implementierung der Potenzierung mit Modul) berechnen, also berechnen n Ziffern werden dauern O(n) Zeit möglicherweise O(n log n).