Ha richiesto un Lavoro di Precisione per il BBP Algoritmo?

Question

Sto cercando di calcolare il nesima cifra di Pi bassa-ambiente di memoria.Come non ho decimali, per me, questo integer solo BBP algoritmo in Python è stato un ottimo punto di partenza.Ho solo bisogno di calcolare una cifra di Pi in un momento. Come posso determinare il minimo che posso impostare D, il "numero di cifre di precisione di lavoro"?

D=4 mi dà molte cifre corrette, ma un paio di cifre, sarà fuori di uno.Ad esempio, il calcolo della cifra 393 con precisione di 4 dà 0xafda, da cui ho estratto la cifra 0xa.Tuttavia, la cifra corretta è 0xb.

Non importa quanto in alto I set D, sembra che il test di un sufficiente numero di cifre trova uno in cui la formula restituisce un valore non corretto.

Ho provato aumentando la precisione, quando la cifra è "vicino" a un altro, ad es.0x3fff o 0x1000, ma non riesce a trovare qualche buona definizione di "chiusura";per esempio, il calcolo a cifre 9798 dà 0xcde6 , che non è molto vicino al 0xd000, ma la cifra corretta è 0xd.

Qualcuno mi può aiutare a capire quanto lavoro di precisione è necessario calcolare una determinata cifra utilizzando questo algoritmo?

Grazie,

modifica
Per Riferimento:

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

Nota che io sono il calcolo di una cifra alla volta, per esempio:

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

Non importa quanto in alto I set D, sembra che il test di un numero sufficiente di cifre trova uno in cui la formula restituisce un valore non corretto.

Si otterrà un errore se si verifica un sufficiente numero di cifre - l'algoritmo non utilizzare con precisione arbitraria, così errori di arrotondamento spettacolo fino alla fine.

La sovrabbondanza di iterazione con pausa quando la cifra non cambia sta per essere difficile determinare il numero minimo di precisione richiesto per un determinato numero di cifre.

La vostra scommessa migliore è quello di determinare empiricamente, idealmente, attraverso il confronto con la sorgente corretta, e aumentando il numero di cifre di precisione fino ad arrivare match, o se l'origine non è disponibile, iniziare con la massima precisione (di cui credo di 14, dal 15 cifre quasi sempre contengono un errore di arrotondamento.)

EDIT:Per essere più precisi, l'algoritmo include un ciclo da 0..n, dove n è la cifra che si vuole calcolare.Ogni iterazione del loop, introdurre una certa quantità di errore.Dopo il loop di un numero sufficiente di volte, l'errore invadere la cifra più significativa che si sono computing, e quindi il risultato sarà sbagliato.

L'articolo di wikipedia utilizza 14 cifre di precisione, e questo è sufficiente per calcolare correttamente il 10**8 cifre.Come ti ho mostrato, un minor numero di cifre di precisione porta ad errori che si verificano in precedenza, in quanto c'è meno precisione e l'errore diventa visibile con un minor numero di iterazioni.Il risultato netto è che il valore di n per il quale siamo in grado di calcolare correttamente una cifra diventa inferiore con un minor numero di cifre di precisione.

Se si dispone di D hex cifre di precisione, che D*4 bit.Con ogni iterazione, un errore di 0.5 bit è introdotto nel bit meno significativo, quindi con 2 iterazioni c'è una possibilità che il LSB è sbagliato.Durante la sommatoria di questi errori si sono aggiunti, e così si sono accumulati.Se il numero di errori che sommati raggiunge il LSB la cifra più significativa, quindi la cifra è estratto sarà sbagliato.Grosso modo, che è quando N > 2**(D-0.75).(Giusto per qualche base logaritmica.)

Empiricamente, estrapolando i dati, sembra una corrispondenza approssimata è N=~(2**(2.05*D)), anche se ci sono pochi datapoint, quindi questo non può essere un preannunciatore esatto.

Il BBP algoritmo che hai scelto è di tipo iterativo, e quindi ci vorrà progressivamente più tempo per calcolare le cifre in sequenza.Per calcolare le cifre 0..n, avrà O(n^2) i passaggi.

L'articolo di wikipedia dà una formula per calcolare l'n-esima cifra che non richiede iterazione, elevamento a potenza e numeri razionali.Questo non subire la stessa perdita di precisione, come l'algoritmo iterativo e si possono calcolare le cifre di pi greco, come necessario in un tempo costante (o, al peggio, di tipo logaritmico, a seconda dell'attuazione dell'elevamento a potenza con il modulo di elasticità), così computing n cifre avrà O(n) il tempo, eventualmente, O(n log n).