Approximations de Pi: Formule de Bailey-Borwein-Plouffe

Soyez le premier à donner votre avis sur cette source.

Vue 3 228 fois - Téléchargée 162 fois

Description

Bonjour,

La formule de Bailey-Borwein-Plouffe ou formule BBP est connue depuis 1995:

Pi = Somme(i>=0) {[4/(8*i+1) - 2/(8*i+4) - 1/(8*i+5) - 1/(8*i+6)] / 16^i}

Elle est particulièrement utilisée pour calculer le n-ième chiffre après la virgule de pi en base 16.

Cet article fait partie de la série CodeS-SourceS: Approximations de Pi.

Pour obtenir "seulement" la précision double, la programmation de cette formule est assez simple, malgré qu'elle permet d'approcher Pi rapidement:
double BBP_A(int n) {
  double pi=0.0;
  for (int i=0; i<n; ++i) {
    int d1=8*i+1, d4=d1+3, d5=d4+1, d6=d5+1;
    pi += (4.0/d1 - 2.0/d4 - 1.0/d5 - 1.0/d6) / (1ll<<(4*i));
  }
  return pi;
} // Pi = Somme (i>=0) {[4/(8*i+1) - 2/(8*i+4) - 1/(8*i+5) - 1/(8*i+6)] / 16^i}


double BBP_B(int n) { // plus condensé
  double pi=9.4/3; // pi = 4/1 - 2/4 - 1/5 - 1/6 = 3.13333...
  for (int i=1,d=12; i<n; ++i,d+=8)
    pi += (4.0/(d-3) - 2.0/d - 1.0/(d+1) - 1.0/(d+2)) / (1ll<<(4*i));
  return pi;
}
Ces deux fonctions "équivalentes" permettent de trouver Pi avec la précision double en 10 itérations !
Et sans racine carrée !

Finalement, voici encore un code correspondant à la seconde formule (celle avec 7 termes, souvent appelée formule de Fabrice Bellard), dérivée de la formule BBP:
// Pi = Somme(i>=0) {[- 32/(4*i+1) - 1/(4*i+3) + 256/(10*i+1) - 64/(10*i+3)
//                    - 4/(10*i+5) - 4/(10*i+7) + 1/(10*i+9)] / -1024^i} / 64
double BBP_C(int n) {
  double pi=0.0, e=1.0;
  for (int i=0; i<n; ++i, e/=-1024) {
    int q=4*i, d=10*i;
    pi += (256.0/(d+1) - 64.0/(d+3) - 4.0/(d+5) -4.0/(d+7) + 1.0/(d+9)
           - 32.0/(q+1) - 1.0/(q+3)) * e;
  }
  return pi/64;
}

double BBP_D(int n) { // plus condensé
  double pi=0.0, e=1.0;
  for (int d=1, q=1, N=4*n; q<N; q+=4, d+=10, e/=-1024) pi += (256.0/d -
    64.0/(d+2) - 4.0/(d+4) -4.0/(d+6) + 1.0/(d+8) - 32.0/q - 1.0/(q+2)) * e;
  return pi/64;
}
Et on trouve Pi avec la précision double en 5 itérations !
 
 
Le Zip contient le seul fichier source BBP.cpp dont voici l'Output:
BBP_A:
  Pi = Somme {[4/(8*i+1) - 2/(8*i+4) - 1/(8*i+5) - 1/(8*i+6)] / 16^i}
  n= 1: pi=3.13333333333333
  n= 2: pi=3.14142246642247
  n= 3: pi=3.14158739034658
  n= 4: pi=3.14159245756744
  n= 5: pi=3.14159264546034
  n= 6: pi=3.14159265322809
  n= 7: pi=3.14159265357288
  n= 8: pi=3.14159265358897
  n= 9: pi=3.14159265358975
  n=10: pi=3.14159265358979
precis: pi=3.14159265358979

BBP_B:
  Pi = Somme {[4/(8*i+1) - 2/(8*i+4) - 1/(8*i+5) - 1/(8*i+6)] / 16^i}
  n= 1: pi=3.13333333333333
  n= 2: pi=3.14142246642247
  n= 3: pi=3.14158739034658
  n= 4: pi=3.14159245756744
  n= 5: pi=3.14159264546034
  n= 6: pi=3.14159265322809
  n= 7: pi=3.14159265357288
  n= 8: pi=3.14159265358897
  n= 9: pi=3.14159265358975
  n=10: pi=3.14159265358979
precis: pi=3.14159265358979

BBP_C:
  Pi = Somme {[- 32/(4*i+1) - 1/(4*i+3) + 256/(10*i+1) - 64/(10*i+3)
               - 4/(10*i+5) - 4/(10*i+7) + 1/(10*i+9)] / -1024^i} / 64
  n= 1: pi=3.14176587301587
  n= 2: pi=3.14159257186839
  n= 3: pi=3.14159265364205
  n= 4: pi=3.14159265358975
  n= 5: pi=3.14159265358979
precis: pi=3.14159265358979

BBP_D:
  Pi = Somme {[- 32/(4*i+1) - 1/(4*i+3) + 256/(10*i+1) - 64/(10*i+3)
               - 4/(10*i+5) - 4/(10*i+7) + 1/(10*i+9)] / -1024^i} / 64
  n= 1: pi=3.14176587301587
  n= 2: pi=3.14159257186839
  n= 3: pi=3.14159265364205
  n= 4: pi=3.14159265358975
  n= 5: pi=3.14159265358979
precis: pi=3.14159265358979


Voir aussi Wiki: Formule BBP
pi314: BBP formula.
 
 
Bonne lecture ...

Codes Sources

A voir également

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.