Nécessité un Travail de Précision pour le BBP Algorithme?

Question

Je cherche à calculer la nth chiffres de Pi dans une faible mémoire de l'environnement.Comme je n'ai pas de décimales est disponible pour moi, c' entier-seulement BBP algorithme en Python a été un excellent point de départ.J'ai seulement besoin de calculer un chiffre de Pi à la fois. Comment puis-je déterminer la plus faible, je peux mettre D, le "nombre de chiffres de la précision de fonctionnement"?

D=4 me donne beaucoup de chiffres corrects, mais quelques chiffres sera désactivé par un.Par exemple, calculer les chiffres 393 avec une précision de 4 me donne 0xafda, dont j'ai extrait les chiffres 0xa.Toutefois, le chiffre correct est 0xb.

Peu importe à quelle hauteur je set D, il semble que le test d'un nombre suffisant de chiffres en trouve un où la formule renvoie une valeur incorrecte.

J'ai essayé d'augmenter la précision lorsque le chiffre est "proche" de l'autre, par exemple0x3fff ou 0x1000, mais ne peut pas trouver une bonne définition de "proche";par exemple, le calcul au chiffre 9798 me donne 0xcde6 , ce qui n'est pas très proche de 0xd000, mais le chiffre correct est 0xd.

Quelqu'un peut-il m'aider à comprendre comment beaucoup de travail de précision est nécessaire pour calculer un chiffre donné à l'aide de cet algorithme?

Merci,

modifier
Pour Référence:

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

Notez que je suis à calculer un chiffre à la fois, par exemple:

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

Peu importe à quelle hauteur je set D, il semble que les tests de dépistage d'un nombre suffisant de chiffres en trouve une où la formule renvoie une valeur incorrecte.

Vous obtiendrez toujours une erreur si vous testez un nombre suffisant de chiffres - l'algorithme n'utilise pas de précision arbitraire, de sorte que les erreurs d'arrondi apparaîtra par la suite.

L'utilisation illimitée de l'itération avec une pause lorsque le chiffre ne change pas va être difficile de déterminer la précision minimale requise pour un nombre donné de chiffres.

Votre meilleur pari est de déterminer de façon empirique, idéalement en comparant avec une source correcte, et en augmentant le nombre de chiffres de précision jusqu'à ce que vous obtenez match, ou si la source n'est pas disponible, commencez avec votre maximum de précision (qui je suppose est de 14 ans, depuis le 15 digits contiennent presque toujours une erreur d'arrondi.)

EDIT:Pour être plus précis, l'algorithme comprend une boucle à partir de 0..n, où n est le chiffre à calculer.Chaque itération de la boucle d'introduire une certaine quantité de l'erreur.Après le bouclage d'un nombre suffisant de fois, l'erreur sera empiéter sur les chiffres plus importantes que vous êtes à l'informatique, et donc le résultat sera mauvais.

L'article de wikipédia utilise les 14 chiffres de précision, et cela est suffisant pour calculer correctement le 10**8 chiffres.Comme vous l'avez montré, moins de chiffres de précision conduit à des erreurs survenant plus tôt, car il y a moins de précision et erreur devient visible avec moins d'itérations.Le résultat net est que la valeur de n pour laquelle on peut calculer correctement un chiffre devient plus faible avec moins de chiffres de précision.

Si vous avez D hex de chiffres de précision, c'est D*4 bits.À chaque itération, une erreur de 0,5 bits est introduit dans le bit le moins significatif, donc avec 2 itérations de la chance de le LSB est faux.Au cours de la sommation, ces erreurs sont ajoutés, et le cumul des.Si le nombre d'erreurs résumé atteint le bit de poids faible dans la plupart chiffre significatif, alors le seul chiffre que vous avez extrait sera mauvais.Grosso modo, c'est lorsque N > 2**(D-0.75).(Bon pour certains logarithmique de base.)

Empiriquement, l'extrapolation de vos données, il semble qu'un ajustement approximatif est N=~(2**(2.05*D)), bien qu'il existe quelques points de données si cela peut ne pas être un indicateur précis.

Le BBP algorithme que vous avez choisi est itératif, et il en faudra de plus en plus de temps à calculer les chiffres de la séquence.Pour calculer les chiffres de 0..n, prendra O(n^2) les étapes.

L'article de wikipédia donne une formule pour calculer le n-ième chiffre qui ne nécessite pas d'itération, juste exponentiation et des nombres rationnels.Cela ne va pas subir le même perte de précision que l'algorithme itératif et vous pouvez calculer un chiffre de pi comme nécessaire en temps constant (ou, au pire, type logarithmique, en fonction de la mise en œuvre de l'exponentiation avec le module), de sorte que le calcul de n les chiffres de prendre O(n) le temps éventuellement O(n log n).