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

Question

J'essayais différentes méthodes pour implémenter un programme qui donne les chiffres de pi de manière séquentielle. J'ai essayé le 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.

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

Answer 1

Comme je suis l'actuel détenteur du record du monde du plus grand nombre de chiffres de pi, je vais ajouter mon deux cents :

À moins que vous n'établissiez 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 effectués à partir de ceux-ci : http://www.numberworld.org/digits/Pi/

---

Mais quand on entre dans le domaine des records du monde, il n'y a rien à quoi se comparer.

Historiquement, l'approche standard pour vérifier que les chiffres calculés sont corrects consiste à recalculer les chiffres à l'aide d'un second algorithme. Ainsi, si l'un des deux calculs échoue, les chiffres obtenus à la fin ne correspondront pas.

Cela fait généralement plus que doubler le temps nécessaire (puisque 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 vous êtes aventuré sur le territoire inexploré des chiffres jamais calculés auparavant et d'un nouveau record mondial.

---

À l'époque où les superordinateurs établissaient des records, deux différents Algorithmes de l'AGA étaient couramment utilisés :

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

Ce sont à la fois O(N log(N)^2) des 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 connue la plus rapide ( Formule de Chudnovsky ) :

Cet algorithme est beaucoup plus difficile à mettre en œuvre, mais il est beaucoup plus rapide que les algorithmes AGM.

Ensuite, nous vérifions les chiffres binaires à l'aide de la fonction Formules BBP pour l'extraction des chiffres .

Cette formule vous permet de calculer des chiffres binaires arbitraires. sin en calculant tous les chiffres qui le précèdent. 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 cette méthode est le suivant :

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

L'inconvénient est que :

1. Une mise en œuvre de la Bailey-Borwein-Plouffe (BBP) est nécessaire.
2. Une étape supplémentaire est nécessaire pour vérifier la conversion du 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 s'en rendre compte puisque toute erreur de calcul se propage aux derniers chiffres.}

---

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é sur ce sujet car, au départ, je n'ai pas donné une description suffisante de son fonctionnement.

J'ai donc tiré cet extrait de mon blog :

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

Calculez A en utilisant l'arithmétique en 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 en savoir plus, consultez mon article de blog Pi - 5 trillions de chiffres .

Answer 2

Sans aucun doute, pour votre objectif (qui, je suppose, n'est qu'un exercice de programmation), la meilleure chose à faire est de vérifier vos résultats par rapport à n'importe quelle liste des chiffres de pi sur le web.

Et comment savoir si ces valeurs sont correctes ? Eh bien, je pourrais dire qu'il existe des moyens informatiques de prouver que l'implémentation d'un algorithme est correcte.

D'un point de vue plus pragmatique, si différentes personnes utilisent différents algorithmes et qu'elles sont toutes d'accord sur (choisissez un nombre) mille (millions, peu importe) décimales, cela devrait vous donner le sentiment chaleureux qu'elles ont bien fait les choses.

Historiquement, William Shanks a publié pi à 707 décimales en 1873. Le pauvre, il s'est trompé en commençant à la 528e décimale.

De façon très intéressante, en 1995 un algorithme a été publié qui avait la propriété de calculer directement le n-iè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 moyen le plus simple de programmer, mais c'est aussi l'un des moyens les plus lents de le faire. Regardez l'article sur le pi sur Wikipedia pour des approches plus rapides.

Answer 3

Vous pourriez utiliser plusieurs approches et voir si elles convergent vers la même réponse. Ou en trouver sur le 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/

Answer 4

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

On peut montrer que les sommes partielles de la série de Taylor s'éloignent de la vraie valeur de pi à un certain multiplicateur du terme suivant.

D'autres moyens d'approximation de pi ont des méthodes similaires pour calculer l'erreur maximale.

Nous le savons car nous pouvons le prouver mathématiquement.

Answer 5

Vous pouvez essayer de calculer sin(pi/2) (o cos(pi/2) ) en utilisant les séries de puissance (assez) rapidement convergentes pour le sin et le cos. (Mieux encore : utiliser diverses formules de doublement pour calculer des valeurs plus proches de la réalité). 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 pourriez utiliser les séries de Taylor comme ci-dessus) est de faire la recherche de racine via Newton. Il existe certainement de meilleurs algorithmes, mais si vous ne voulez pas vérifier des tonnes de chiffres, celui-ci devrait suffire (et il n'est pas si difficile à mettre en œuvre, et vous n'avez besoin que d'un peu de calcul pour comprendre pourquoi il fonctionne).