Approximations de Pi

Commenter

Contenu du snippet

Bonjour,

Voici toute une série d'articles "Approximations de Pi" qui comporte des algorithmes plus ou moins simples, plus ou moins rapides.
Dans tous les codes exposés, on se borne aux calculs de précision "double" (réels sur 64 bits), ce qui nous limitera à une quinzaine de chiffres décimaux.

Remarque sur la "précision double":
Les formules et algorithmes "modernes" atteignent cette précision en quelques rares itérations !
Pour pouvoir les utiliser pleinement, il faudrait se baser sur des systèmes de nombres bien plus étendus (tels que GMP, BigInt, ?) et calculer un nombre de chiffres précis beaucoup plus grand.
J'espère que cette série vous aidera à choisir un ou plusieurs algorithmes et présenter des articles qui calculent Pi à mille, un million, un milliard, etc. de chiffres.


Le tableau ci-dessous comporte les colonnes ch/1000000it et it/15ch:

  - Algorithmes lents ==> ch/1000000it:
    Nombre de chiffres après la virgule obtenus après un million d'itérations.

  - Algorithmes rapides ==> it/15ch:
    Nombre d'itérations nécessaires pour calculer pi avec la précision double.

 Titre   Année   ch/1000000it   it/15ch  
 Formule de Madhava de Sangamagrama    ~1400       28
 Produit de Wallis    1655               5 
 Formule de Newton    1666       22
 Fractions continues   ~1680    32000 
 Formule de Leibniz    1682               6 
 Formule de Lagny    1682       30
 Formule de Viète    1692       24
 Formule de Machin    1706       10
 Formule de Euler    1735       50
 Formules avec nombres de Fibonacci       ?      (28)
 Formule avec nombres premiers       ?               8 
 Formule du Nombre d'Or       ?       32
 Méthode Monte-Carlo       ?               2
 Formule de Ramanujan    1910        2
 Algorithme de Brent-Salamin    1976        3
 Formule et série de Gosper       ?    23 ¦ 12
 Algorithmes de Borwein    1985     (1) 2
 Formule de Chudnovsky    1987     (1) 2
 Formule de Bailey-Borwein-Plouffe    1995    10 ¦ 5
 Formule de Adamchick-Wagon    1997       22
  ^^^ Cliquez sur un titre ^^^

Connaitriez-vous d'autres algorithmes ou formules qu'il serait intéressant d'ajouter ?

A titre d'exemple, voici un code introductif qui montre (partiellement) la manière dont sont traités les différents algorithmes: 
#include <stdio.h>
#include <math.h>

double Leibniz(int n) {
  double pi=1.0;
  for (int i=1; i<=n; ++i) pi += ((i&1) ? -1.0 : 1.0) / (2*i + 1);
  return 4*pi;
} // pi = 4*{1 - 1/3 + 1/5 - 1/7 + 1/9 - 1/11 + ...}

double Viete(int n) {
  double q=0.0, pi=2.0;
  for (int i=0; i<n; ++i) {
    q = sqrt(2.0+q);
    pi *= 2.0/q;
  }
  return pi;
} // Pi = 2 * 2/sqrt(2) * 2/sqrt(2+sqrt(2)) * 2/sqrt(2+sqrt(2+sqrt(2)) * ...

void main() {
  printf("Leibniz: pi = 4*{1 - 1/3 + 1/5 - 1/7 + 1/9 - 1/11 + ...}n");
  for (int n=10; n<=1000000; n*=10) printf("  n=%7i: pi=%.14fn",n,Leibniz(n));
  printf("     precis: pi=3.14159265358979n");

  printf("nViete: pi = ");
  printf("2 * 2/sqrt(2) * 2/sqrt(2+sqrt(2)) * 2/sqrt(2+sqrt(2+sqrt(2)) *...n");
  for (int n=4; n<=24; n+=4) printf("  n=%2i: pi=%.14fn",n,Viete(n));
  printf("precis: pi=3.14159265358979n");

  getchar();
}

Et qui donne l'output: 
Leibniz: pi = 4*{1 - 1/3 + 1/5 - 1/7 + 1/9 - 1/11 + ...}
  n=     10: pi=3.23231580940559
  n=    100: pi=3.15149340107099
  n=   1000: pi=3.14259165433954
  n=  10000: pi=3.14169264359053
  n= 100000: pi=3.14160265348972
  n=1000000: pi=3.14159365358877
     precis: pi=3.14159265358979

Viete: pi = 2 * 2/sqrt(2) * 2/sqrt(2+sqrt(2)) * 2/sqrt(2+sqrt(2+sqrt(2)) *...
  n= 4: pi=3.13654849054594
  n= 8: pi=3.14157294036709
  n=12: pi=3.14159257658487
  n=16: pi=3.14159265328899
  n=20: pi=3.14159265358862
  n=24: pi=3.14159265358979
precis: pi=3.14159265358979

Par la suite, je pense déposer une autre série d'articles consacrée aux
"calculs beaucoup plus précis de Pi".
Mais, ayant très peu d'expérience avec les "grands nombres" (GMP, BigInt, ?), conseillez-moi pour installer, tester et utiliser l'une ou l'autre de ces librairies.
 
 
Quelques liens intéressants
Wiki: Pi , L'Histoire de Pi, Approximations of pi
CodeS-SourceS: Calcul de pi
NOMBRES: Constante Pi
Des trucs et des maths: Le nombre pi
Gérard Sookahet: Formules et algorithmes pour évaluer pi
Pi314: L'univers de pi
Fabien Durand: La longue histoire de Pi
Wolfram MathWorld: Pi Formulas
Math²: Le calcul du nombre Pi
 
 
Moyen mnémotechnique pour pi = 3,1415926535 :
  Que j'aime à faire apprendre ce nombre utile aux sages
La longueur de chaque mot donne une décimale.
 
 
Merci d'avance pour vos éventuels conseils, suggestions ou corrections.

Bonne lecture ...

Compatibilité : 0: Annonce d'une série d'approximations de Pi

A voir également

Du même auteur (William VOIROL)