781 votes

Comment déterminer si mon calcul de pi est exacte ?

J'ai essayé différentes méthodes pour mettre en œuvre un programme qui donne les chiffres de pi de manière séquentielle. J'ai essayé la série de Taylor de la méthode, mais il s'est avéré convergent très lentement (quand je compare mon résultat en ligne avec le valeurs après un certain temps). De toute façon, je suis en train de meilleurs algorithmes.

Ainsi, alors que l'écriture du programme, j'ai coincé sur un problème, comme avec tous les algorithmes: Comment puis-je savoir que l' n chiffres que j'ai obtenus sont exacts?

1641voto

Mysticial Points 180300

Depuis que je suis l'actuel détenteur du record du monde pour la plupart des chiffres de pi, je vais ajouter mon grain de sel:

Sauf si vous êtes l'établissement d'un nouveau record du monde, la pratique courante est juste pour vérifier le calcul des chiffres contre les valeurs connues. Donc, c'est assez simple.

En fait, j'ai une page web qui répertorie des extraits de chiffres dans le but de vérifier les calculs contre eux: http://www.numberworld.org/digits/Pi/


Mais quand on est dans le monde record du territoire, il n'y a rien à comparer.

Historiquement, l'approche standard pour vérifier que le calcul de chiffres corrects est de recalculer les chiffres à l'aide d'un second algorithme. Ainsi, si l'un calcul va mal, les chiffres à la fin ne correspond pas.

Ce n'est généralement plus du double de la quantité de temps nécessaire (depuis le deuxième algorithme est généralement plus lent). Mais c'est la seule manière de vérifier le calcul des chiffres une fois que vous avez erré dans le territoire inconnu de jamais-avant-calculée chiffres et un nouveau record du monde.


Retour dans les jours où les supercalculateurs ont les dossiers, deux AGA algorithmes couramment utilisés:

Ce sont les deux O(N log(N)^2) algorithmes qui ont été assez faciles à mettre en œuvre.

Cependant, de nos jours, les choses sont un peu différentes. Dans les trois derniers records du monde, au lieu d'effectuer les deux calculs, nous avons effectué un seul calcul à l'aide de la manière la plus rapide connue de formule (Formule de Chudnovsky):

Enter image description here

Cet algorithme est beaucoup plus difficile à mettre en œuvre, mais il est beaucoup plus rapide que l'AGA algorithmes.

Ensuite, nous vérifions les chiffres binaires en utilisant les formules BBP pour les chiffres de l'extraction.

Enter image description here

Cette formule permet de calculer arbitraire chiffres binaires sans le calcul de tous les chiffres avant. Il est donc utilisé pour vérifier les derniers calculée chiffres binaires. Par conséquent, il est beaucoup plus rapide qu'un plein de calcul.

L'avantage, c'est:

  1. Seul un calcul coûteux est nécessaire.

L'inconvénient est:

  1. Une mise en œuvre de l' Bailey–Borwein–Plouffe (BBP) formule est nécessaire.
  2. Une étape supplémentaire est nécessaire pour vérifier la base de la conversion de binaire en décimal.

J'ai parcouru rapidement quelques détails de pourquoi vérifier les derniers chiffres implique que tous les chiffres sont corrects. Mais il est facile de voir cela, car toute erreur de calcul de propagation les derniers chiffres.


Maintenant, cette dernière étape (la vérification de la conversion) est en fait assez important. L'un des précédent record du monde titulaires de fait nous a appelés à sortir sur ce parce que, d'abord, je ne lui donne pas une description suffisante de la façon dont il a travaillé.

Donc j'ai tiré cet extrait de mon blog:

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

Enter image description here


Calculer à l'aide de la base de 10 arithmétique et B à l'aide de l'arithmétique binaire.

enter image description here

Si A = B, puis avec la "très forte probabilité", la conversion est correcte.


Pour en savoir plus, voir mon blog Pi - 5 Billions de Chiffres.

48voto

Larry Smith Points 281

Sans aucun doute, pour vos fins (ce qui je suppose est juste un exercice de programmation), la meilleure chose à faire est de vérifier vos résultats contre les listes de chiffres de pi sur le web.

Et comment savons-nous que ces valeurs sont correctes? Eh bien, je pourrais dire qu'il y a de l'informatique-y les moyens de prouver qu'une mise en œuvre d'un algorithme est correct.

De manière plus pragmatique, si différentes personnes utilisent des algorithmes différents, et ils sont tous d'accord pour (choisir un nombre) mille (millions de dollars, soit) décimales, ce qui devrait vous donner une ambiance chaleureuse et douillette qu'ils ont obtenu le droit.

Historiquement, William Shanks publié pi à 707 décimales en 1873. Pauvre gars, il a fait une erreur de départ à la 528th décimale.

Très intéressant, en 1995 , un algorithme a été publié , qui avait la propriété qui serait directement calculer le n-ième digit (base 16) de pi sans avoir à calculer tous les chiffres précédents!

Enfin, j'espère que votre algorithme initial n'était pas pi/4 = 1 - 1/3 + 1/5 - 1/7 + ... Que peut être le plus simple à programmer, mais c'est aussi l'un des plus lents de façons de le faire. Découvrez la pi article sur Wikipédia pour accélérer les démarches.

21voto

airza Points 1950

Vous pourriez utiliser des approches multiples et voir si elles convergent vers la même réponse. Ou saisir certains de la ' net. L’algorithme de Chudnovsky est généralement utilisé comme une méthode très rapide de calcul de pi. http://www.Craig-Wood.com/Nick/Articles/pi-Chudnovsky/

15voto

Yakk Points 31636

La série de Taylor est une façon d’approximer pi. Comme l’a noté, elle converge lentement.

Les sommes partielles de la série de Taylor peuvent être démontrés au sein d’un multiplicateur de la prochaine période loin de la vraie valeur de pi.

Autres moyens d’approximation de pi ont des manières semblables pour calculer l’erreur max.

Nous le savons parce que nous pouvons le prouver mathématiquement.

5voto

user1974703 Points 29

Vous pouvez essayer de calcul de sin(pi/2) (ou cos(pi/2)) à l'aide de la (relativement) rapidement convergence des séries de puissances de sin et cos. (Encore mieux: utiliser plusieurs doublement des formules pour calculer la plus proche de x=0 pour accélérer la convergence.)

BTW, mieux que d'utiliser la série de tan(x) est, avec le calcul de dire que cos(x) comme une boîte noire (par exemple, vous pouvez utiliser la série de taylor en tant que ci-dessus) est de faire la recherche de racines par Newton. Il y a certainement de meilleurs algorithmes de là-bas, mais si vous ne voulez pas de vérifier des tonnes de chiffres, cela devrait suffire (et ce n'est pas que difficile à mettre en œuvre, et vous avez seulement besoin d'un peu de calcul différentiel et intégral à comprendre pourquoi il fonctionne.)

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X