Question Comment puis-je déterminer si mon calcul de pi est exact?


J'essayais différentes méthodes pour implémenter un programme qui donne les chiffres de pi séquentiellement. J'ai essayé le Taylor série méthode, mais il s'est avéré converger extrêmement lentement (quand j'ai comparé mon résultat avec les valeurs en ligne après un certain temps). De toute façon, j'essaie de meilleurs algorithmes.

Ainsi, tout en écrivant le programme je suis resté coincé sur un problème, comme avec tous les algorithmes: Comment puis-je savoir que le n les chiffres que j'ai calculés sont-ils exacts?


732
2018-01-11 17:15


origine


Réponses:


Depuis que je suis le détenteur du record du monde actuel pour le plus de chiffres de pi, je vais ajouter mon deux centimes:

À moins que vous définissiez réellement un nouveau record du monde, la pratique courante consiste simplement à vérifier les chiffres calculés par rapport aux valeurs connues. 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 à leur encontre: http://www.numberworld.org/digits/Pi/


Mais quand vous entrez dans un territoire de record du monde, il n'y a rien à comparer.

Historiquement, l'approche standard pour vérifier que les chiffres calculés sont corrects est de recalculer les chiffres en utilisant un second algorithme. Donc, si l'un ou l'autre calcul est mauvais, les chiffres à la fin ne correspondront pas.

Cela fait généralement plus que doubler le temps nécessaire (puisque le second algorithme est généralement plus lent). Mais c'est la seule façon de vérifier les chiffres calculés une fois que vous avez erré dans le territoire inexploré de chiffres jamais-avant-calculés et un nouveau record du monde.


Retour à l'époque où les superordinateurs établissaient les records, deux différents Algorithmes AGM étaient couramment utilisés:

Ce sont les deux O(N log(N)^2) algorithmes qui étaient 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 deux calculs, nous avons effectué un seul calcul en utilisant la formule la plus rapide connue (Chudnovsky Formule):

Enter image description here

Cet algorithme est beaucoup plus difficile à implémenter, mais il est beaucoup plus rapide que les algorithmes AGM.

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

Enter image description here

Cette formule vous permet de calculer des nombres binaires arbitraires sans pour autant calculer tous les chiffres avant. Il est donc utilisé pour vérifier les derniers chiffres binaires calculés. Il est donc beaucoup plus rapide qu'un calcul complet.

L'avantage de ceci est:

  1. Un seul calcul coûteux est nécessaire.

L'inconvénient est:

  1. Une mise en œuvre de Bailey-Borwein-Plouffe (BBP) formule est nécessaire.
  2. Une étape supplémentaire est nécessaire pour vérifier la conversion de la base de données binaires en décimales.

J'ai passé en revue certains détails de pourquoi la vérification des derniers chiffres implique que tous les chiffres sont corrects. Mais il est facile de voir cela puisque toute erreur de calcul se propagera aux derniers chiffres.


Maintenant, cette dernière étape (vérification de la conversion) est en fait assez importante. Un des détenteurs du record du monde précédent nous a effectivement appelé parce que, initialement, je n'ai pas donné une description suffisante de la façon dont cela fonctionnait.

J'ai donc extrait cet extrait de mon blog:

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

Enter image description here

Calculer A en utilisant l'arithmétique de base 10 et B en utilisant l'arithmétique binaire.

Enter image description here

Si A = B, puis avec "une probabilité extrêmement élevée", la conversion est correcte.


Pour plus de lecture, voir mon article de blog Pi - 5 Trillion Digits.


1578
2018-01-11 17:28



Sans aucun doute, pour vos besoins (que je suppose est juste un exercice de programmation), la meilleure chose est de vérifier vos résultats par rapport à l'une des listes des chiffres de pi sur le web.

Et comment savons-nous que ces valeurs sont correctes? Eh bien, je pourrais dire qu'il existe des moyens informatiques pour démontrer qu'une implémentation d'un algorithme est correcte.

Plus pragmatiquement, si des personnes différentes utilisent des algorithmes différents, et ils sont tous d'accord pour choisir un millier de décimales, cela devrait vous donner un sentiment flou qu'ils ont bien compris.

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

Très intéressant, en 1995 un algorithme a été publié qui avait la propriété qui calculerait directement le nième chiffre (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 + ... C'est peut-être le programme le plus simple à programmer, mais c'est aussi l'un des moyens les plus lents de le faire. Check-out l'article de pi sur Wikipedia pour des approches plus rapides.


47
2018-01-11 17:44



Vous pouvez utiliser plusieurs approches et voir si elles convergent vers la même réponse. Ou prenez-en un peu sur le net. L'algorithme de Chudnovsky est généralement utilisé comme méthode de calcul très rapide de pi. http://www.craig-wood.com/nick/articles/pi-chudnovsky/


20
2018-01-11 17:21



La série Taylor est une façon d'approximer pi. Comme indiqué, il converge lentement.

Les sommes partielles de la série de Taylor peuvent être montrées être dans un certain multiplicateur du terme suivant loin de la vraie valeur de pi.

D'autres moyens d'approximation de pi ont des façons similaires de calculer l'erreur max.

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


14
2018-01-11 17:24



Vous pourriez essayer l'informatique sin(pi/2) (ou cos(pi/2) d'ailleurs) en utilisant la série de puissances convergentes (assez) rapidement pour sin et cos. (Encore mieux: utilisez diverses formules de doublage pour calculer plus près x=0 pour une convergence plus rapide.)

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


4
2018-01-13 19:09