Approximations de Pi: Formule avec nombres premiers

Télécharger le projet
Commenter

Description

Bonjour,

Il existe un produit infini qui donne la valeur exacte de Pi² en utilisant la suite des nombres premiers:
Pi² = 6 * Produit(p=2,3,5,7,11,13,17,...) {1 / (1 - 1/p²)}
Ce produit infini correspond en fait à la fonction Zêta de Riemann: Zêta(2) = Pi²/6.
MeL: Fonction zêta et nombres premiers

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

Petit rappel sur les nombres premiers: Un nombre entier naturel est premier, si l'ensemble de ses diviseurs ne contient que deux éléments : 1 et le nombre lui-même.
Voir CodeS-SourceS: Nombres premiers, Liste de nombres premiers.

Pour calculer les 1'000'000 premiers nombres premiers, utilisons le Crible d'Eratosthène, défini par la routine assez simple Sieve() à l'aide de la boucle sur K: 
const int NN=16000000, N=(NN-1)/2;
bool sv[N];
int prm[665000]={2};

void Sieve() { // sv[i]=true  ssi  2*i+3 est premier
  for (int i=0; i<N; i++) sv[i] = true;
  for (int i=0, p=3, pp=9; pp<=NN; i++, p+=2, pp=p*p)
    if (sv[i]) // p is prime
      for (int j=(pp-3)/2; j<N; j+=p) sv[j] = false;
}

// ...
  int K=0;
  for (int i=0; i<N; i++)
    if (sv[i]) prm[++K] = 2*i+3; // prm = {2,3,5,7,11,13,17,...}
// ...
On pourrait utiliser des algorithmes plus sophistiqués, plus rapides et moins gourmant en mémoire (voir les liens ci-dessus).

Voici un code qui permet d'approcher Pi à l'aide d'une liste de nombres premiers: 
double Premiers_A(int n) {
  double p, pi=6;
  for (int k=0; k<n; ++k) {
    p=prm[k]; // prm[] = {2,3,5,7,11,13,17,...}
    pi *= 1.0/(1.0-1.0/(p*p));
  }
  return sqrt(pi);
} // Pi² = 6 * Produit(p=2,3,5,7,11,13,17,...) {1 / (1 - 1/p²)}
Avec un million d'itérations, on obtient pi qu'avec 7 chiffres corrects après la virgule !

Les deux fonctions suivantes Premiers_B et Premiers_C du Zip sont des variantes équivalentes.

La seconde formule ne donne une efficacité que légèrement meilleure (8 chiffres): 
double Premiers_D(int n) {
  double p, q, pi=31185.0/2;
  for (int k=0; k<n; ++k) {
    p=1.0/prm[k]; p=p*p; q=p*p;
    pi *= 1.0/(1 + p + q + p*q + q*q);
  }
  return sqrt(sqrt(sqrt(pi)));
} // Pi^8 = 31185/2 * Produit(p=premier) {1 / (1 + p^-2 + p^-4 + p^-6 + p^-8)}

Les algorithmes basés sur les nombres premiers sont donc très peu efficaces.
Mais ce qui est surprenant et passionnant, c'est le lien qu'ils établissent entre le "monde" de Pi et celui de l'ensemble les nombres premiers, qui, à priori, semblent complètement différents et séparés !.

Le Zip contient le seul fichier source Premier.cpp dont voici l'Output: 
1031129 nombres premiers calculés !

Les 160 premiers nombres premiers:
 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103
107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211
223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331
337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449
457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587
593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709
719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853
857 859 863 877 881 883 887 907 911 919 929 937 941

Premiers_A:
  n=     10: pi=3.13024327217142
  n=    100: pi=3.14119266049470
  n=   1000: pi=3.14157270300053
  n=  10000: pi=3.14159145460337
  n= 100000: pi=3.14159257315263
  n=1000000: pi=3.14159264788191
     précis: pi=3.14159265358979

Premiers_B:
  n=     10: pi=3.13024327217142
  n=    100: pi=3.14119266049470
  n=   1000: pi=3.14157270300053
  n=  10000: pi=3.14159145460267
  n= 100000: pi=3.14159257314418
  n=1000000: pi=3.14159264779451
     précis: pi=3.14159265358979

Premiers_C:
  n=     10: pi=3.13024327217142
  n=    100: pi=3.14119266049470
  n=   1000: pi=3.14157270300053
  n=  10000: pi=3.14159145460267
  n= 100000: pi=3.14159257314418
  n=1000000: pi=3.14159264779451
     précis: pi=3.14159265358979

Premiers_D:
  n=     10: pi=3.14443642276059
  n=    100: pi=3.14169265982180
  n=   1000: pi=3.14159764125691
  n=  10000: pi=3.14159295333665
  n= 100000: pi=3.14159267370120
  n=1000000: pi=3.14159265503974
     précis: pi=3.14159265358979


Gérard Sookahet: Formules et algorithmes pour évaluer pi
 
 
Bonne lecture ...
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

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.

Du même auteur (William VOIROL)