Comment déterminer si mon calcul de pi est précis?

J'essayais différentes méthodes pour implémenter un programme qui donne les chiffres de pi séquentiellement. J'ai essayé la méthode de la série Taylor , mais elle s'est avérée converger extrêmement lentement (lorsque j'ai comparé mon résultat avec les valeurs en ligne après un certain temps). Quoi qu'il en soit, j'essaie de meilleurs algorithmes.

Donc, en écrivant le programme, je suis resté coincé sur un problème, comme avec tous les algorithmes: comment savoir que les nchiffres que j'ai calculés sont exacts?

Puisque je suis le détenteur du record du monde actuel pour le plus de chiffres de pi, j'ajouterai mes deux cents :

Sauf si vous établissez 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 donc assez simple.

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

Mais lorsque vous entrez sur un territoire record, il n'y a rien à comparer.

Historiquement, l'approche standard pour vérifier que les chiffres calculés sont corrects consiste à recalculer les chiffres à l'aide d'un deuxième algorithme. Donc, si l'un des calculs tourne mal, les chiffres à la fin ne correspondront pas.

Cela fait généralement plus du double du temps nécessaire (car le deuxième algorithme est généralement plus lent). Mais c'est le seul moyen de vérifier les chiffres calculés une fois que vous avez erré dans le territoire inexploré de chiffres jamais calculés auparavant et d'un nouveau record du monde.

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

• Algorithme de Gauss – Legendre
• L'algorithme de Borwein

Ce sont à la fois O(N log(N)^2) algorithmes assez faciles à implémenter.

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 n'avons effectué qu'un seul calcul en utilisant la formule connue la plus rapide (formule de Chudnovsky ):

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 les formules BBP pour l'extraction des chiffres .

Cette formule vous permet de calculer des chiffres binaires arbitraires sans calculer tous les chiffres précédents. 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 la formule Bailey – Borwein – Plouffe (BBP) est nécessaire.
2. Une étape supplémentaire est nécessaire pour vérifier la conversion radix de binaire en décimal.

_{J'ai passé sous silence certains détails expliquant pourquoi la vérification des derniers chiffres implique que tous les chiffres sont corrects. Mais il est facile de voir cela car toute erreur de calcul se propagera jusqu'aux derniers chiffres.}

Maintenant, cette dernière étape (vérification de la conversion) est en fait assez importante. L'un des précédents détenteurs du record du monde nous a en fait appelés à ce sujet car, au départ, je n'avais pas suffisamment décrit comment cela fonctionnait.

J'ai donc extrait cet extrait de mon blog:

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

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

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

Pour plus de lecture, consultez mon article de blog Pi - 5 milliards de chiffres .

Sans aucun doute, pour vos besoins (ce qui, je suppose, n'est qu'un exercice de programmation), la meilleure chose est de vérifier vos résultats par rapport à l'une des listes de 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 de prouver qu'une implémentation d'un algorithme est correcte.

Plus pragmatique, si différentes personnes utilisent différents algorithmes et acceptent toutes (de choisir un nombre) mille (millions, peu importe) décimales, cela devrait vous donner un sentiment flou et chaleureux qu'elles l'ont bien compris.

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

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

Vous pouvez utiliser plusieurs approches et voir si elles convergent vers la même réponse. Ou prenez-en sur le net. L'algorithme 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/

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

On peut montrer que les sommes partielles de la série de Taylor se situent à l'intérieur d'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 maximale.

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

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

BTW, mieux que d'utiliser des séries pour l' tan(x)est, avec l'informatique cos(x)comme une boîte noire (par exemple, vous pouvez utiliser la série taylor comme ci-dessus) consiste à rechercher la racine 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 difficile à mettre en œuvre, et vous n'avez besoin que d'un peu de calcul pour comprendre pourquoi cela fonctionne.)