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

Puisque je suis le détenteur actuel du record du monde pour le plus grand nombre de chiffres de pi, j’appendai mes deux cents :

À moins de définir un nouveau record du monde, la pratique courante consiste à vérifier les chiffres calculés par rapport aux valeurs connues. Donc, c’est assez simple.

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

Mais quand on entre en territoire de record mondial, il n’y a rien à comparer.

Historiquement, l’approche standard pour vérifier que les chiffres calculés sont corrects consiste à recalculer les chiffres en utilisant un deuxième algorithme. Donc, si l’un des calculs est mauvais, les chiffres à la fin ne correspondent 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 avez parcouru le territoire inexploré des chiffres jamais calculés auparavant et un nouveau record du monde.

À l’époque où les superordinateurs configuraient les enregistrements, deux algorithmes AGM différents étaient couramment utilisés:

• Algorithme Gauss – Legendre
• L’algorithme de Borwein

Ce sont les deux algorithmes O(N log(N)^2) 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 n’avons effectué qu’un seul calcul utilisant la formule la plus rapide connue (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 binarys en utilisant les formules BBP pour l’extraction des chiffres .

Cette formule vous permet de calculer des chiffres binarys arbitraires sans calculer tous les chiffres avant. Il est donc utilisé pour vérifier les derniers chiffres binarys calculés. C’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 de base en binary en décimal.

_{J’ai passé en revue certains détails pour lesquels 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 aux derniers chiffres.}

Maintenant, cette dernière étape (vérification de la conversion) est en réalité assez importante. L’un des précédents détenteurs de records du monde nous a en fait appelé parce que, dans un premier temps, je n’avais pas suffisamment expliqué comment cela fonctionnait.

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

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

Calculer A en utilisant l’arithmétique de base 10 et B en utilisant l’arithmétique binary.

Si A = B , alors avec “extrêmement haute probabilité”, la conversion est correcte.

Pour plus de lecture, voir mon blog post Pi – 5 milliards de chiffres .

Sans aucun doute, pour vos besoins (que je présume être un simple exercice de programmation), la meilleure chose à faire est de vérifier vos résultats par rapport aux listes des chiffres de pi sur le Web.

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

De manière plus pragmatique, si différentes personnes utilisent des algorithmes différents, et si elles sont toutes d’accord pour (choisir un nombre) de décimales, cela devrait vous donner l’impression qu’elles ont bien compris.

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

De manière très intéressante, en 1995, un algorithme a été publié avec 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’une des manières les plus lentes de le faire . Consultez 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 dans le filet. L’algorithme de Chudnovsky est généralement utilisé comme une méthode très rapide pour calculer pi. http://www.craig-wood.com/nick/articles/pi-chudnovsky/

La série de Taylor est un moyen d’approcher pi. Comme indiqué, il converge lentement.

On peut montrer que les sums partielles de la série de Taylor se situent dans un certain multiplicateur du terme suivant loin de la valeur réelle de pi.

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

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

Vous pouvez essayer de calculer sin(pi/2) (ou cos(pi/2) ) en utilisant la série de puissances (assez) rapidement convergentes pour sin et cos. (Mieux encore: utilisez différentes formules de dédoublement pour calculer plus proche de x=0 pour une convergence plus rapide.)

BTW, mieux que d’utiliser des séries pour tan(x) est, avec le calcul 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 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 compliqué à mettre en œuvre, et vous n’avez besoin que d’un peu de calcul pour comprendre pourquoi).