Nombres premiers: crible d'Eratosthène

Télécharger le projet
Commenter

Description

J'ai commencé à diffuser dans CodeS-SourceS, Javascript, Divers quelques codes qui concernent les nombres premiers:

premiers: essais de division
Nombres premiers: essais de division avec liste
Nombres premiers: crible d'Eratosthène
Nombres premiers: crible d'Atkin

Comme Javascript est loin d'être performant, je présente ici (sous C/C++/C++.NET) des optimisations de quelques codes intéressants.
De plus, ecrits en C, ces codes me permettent des tests avec mx = un milliard,
( 1000000000 ou 1 000 000 000 ou 1'000'000'000 ou 10^^9 ou billion en anglais )
ou même plus, alors que Javascript se plante !

Accédez à la version actualisée de l'introduction et résumé sur les nombres premiers, complétée de mesures des temps d'exécution: ICI.
 
 

Nombres premiers: crible d'Eratosthène


Nous nous basons sur le code Javascript Sieve3.js: 
// i  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 ...
// p  3  5  7  9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 ...

function Sieve(mx) { // Sieve3.js: mx>=3
  var h=(mx-1)>>1,i,j,p,pp,sv=[]; // sv=new Array(h)
  for (i=0; i<h; i++) sv[i]=true;
  for (i=0,p=3,pp=9; pp<=mx; i++,p+=2,pp=p*p)
    if (sv[i]) // p is prime
      for (j=(pp-3)/2; j<h; j+=p) sv[j]=false;
  return sv; // 2 is not included
}

 
 

SieveA


KX me propose une très bonne traduction de la fonction Sieve (voir sous Commentaires: Crible d'Eratosthène).
J'y remplace simplement le type char par bool: 
#include <time.h>
#include <stdio.h>
#include <windows.h>

typedef unsigned _int32 u32;

bool* Sieve(u32 mx) { // Crible d'Eratosthène
  u32 i, j, p, pp, h=(mx-1)/2; // nombres impairs
  bool* sv=(bool*)malloc(sizeof(bool)*h);
    
  for (i=0; i<h; i++) sv[i]=true;
  for (i=0, p=3, pp=9; pp<=mx; i++, p+=2, pp=p*p)
    if (sv[i]) // p is prime
      for (j=(pp-3)/2; j<h; j+=p) sv[j]=false;
  return sv; // 2 non inclus
}

int main() { // SieveA
  clock_t t;
  u32 i, m, n;
  bool* sv;

  printf("SieveA (Crible d'Eratosthene):");
  for (m=10; m<=1000000000; m*=10) {
    t=GetTickCount();
    sv=Sieve(m);
    t=GetTickCount()-t;
    for (i=0, n=1; i<(m-1)/2; i++) if (sv[i]) n++;
    free(sv);
    printf("nm=%d, n=%d, t=%d ms", m , n, t);
  }
  getchar();
}

Temps d'exécution:
m=10, n=4, t=0 ms
m=100, n=25, t=0 ms
m=1000, n=168, t=0 ms
m=10000, n=1229, t=0 ms
m=100000, n=9592, t=0 ms
m=1000000, n=78498, t=0 ms
m=10000000, n=664579, t=31 ms
m=100000000, n=5761455, t=592 ms
m=1000000000, n=50847534, t=7239 ms
 
 

SieveB


Essayons d'utiliser la notion de "pointeur", dans le but de remplacer dans la boucle intérieure sv[j]=false par *s=false. 
#include <time.h>
#include <stdio.h>
#include <windows.h>

typedef unsigned _int32 u32;

bool* Sieve(u32 mx) { // Optimisation des "pointeurs"
  u32 p, pp, h=(mx-1)/2; // nombres impairs
  bool *sv=(bool*)malloc(sizeof(bool)*h), *s, *q, *z=sv+h;
    
  for (s=sv; s<z; s++) *s=true;
    for (q=sv, p=3, pp=9; pp<=mx; q++, p+=2, pp=p*p)
    if (*q) // p is prime
      for (s=sv+((pp-3)>>1); s<z; s+=p) *s=false;
    return sv; // 2 non inclus
}

int main() { // SieveB
  clock_t t;
  u32 i, m, n;
  bool* sv;

  printf("SieveB (Crible d'Eratosthene):");
  for (m=10; m<=1000000000; m*=10) {
    t=GetTickCount();
    sv=Sieve(m);
    t=GetTickCount()-t;
    for (i=0, n=1; i<(m-1)/2; i++) if (sv[i]) n++;
    free(sv);
    printf("nm=%d, n=%d, t=%d ms", m , n, t);
  }
  getchar();
}

Temps d'exécution:
m=10, n=4, t=0 ms
m=100, n=25, t=0 ms
m=1000, n=168, t=0 ms
m=10000, n=1229, t=0 ms
m=100000, n=9592, t=0 ms
m=1000000, n=78498, t=0 ms
m=10000000, n=664579, t=31 ms
m=100000000, n=5761455, t=592 ms
m=1000000000, n=50847534, t=7223 ms

L'amélioration n'est pas flagrante, ce qui montre que le compilateur utilisé est performant (Visual C++ 2008 en Release).
 
 

SieveC


Théoriquement, un boolean ne devrait utiliser qu'un seul bit, alors qu'un bool en utilise 8 (et encore plus en Javascript) !
Un "array of bool" (avec 8 fois moins de mémoire) peut être simulé à l'aide du code élémentaire que j'ai "bricolé": 
// Simulation d'un "BitSet32" basé sur: typedef unsigned _int32 u32

u32* BitSet32(u32 len, bool ini) {
  u32 i, n=(len+31)>>5, b=(ini)? 0XFFFFFFFF: 0;
  u32* bs=(u32*)malloc(n*sizeof(u32));
  for (i=0,b=(ini=; i<n; i++) bs[i]=b;
  return bs;
}
void SetTrue(u32* bs, u32 i) {bs[i>>5] |= 1<<(i&31);}
void SetFalse(u32* bs, u32 i) {bs[i>>5] &= (~(1<<(i&31)));}
bool Get(u32* bs, u32 i) {return ((bs[i>>5] & (1<<(i&31)))!=0);}

Pour des raisons de performance, je n'utilise pas directement ces fonctions, mais j'introduis le code correspondant "in line": 
#include <time.h>
#include <stdio.h>
#include <windows.h>

typedef unsigned _int32 u32;

u32* Sieve(u32 mx) { // Utilisation bitset
  u32 i, j, p, pp, h=(mx-1)/2, n=(h+31)>>5; // nombres impairs
  u32* sv=(u32*)malloc(n*sizeof(u32));
  for (i=0; i<n; i++) sv[i]=0XFFFFFFFF; // All true
    for (i=0, p=3, pp=9; pp<=mx; i++, p+=2, pp=p*p)
      if (sv[i>>5]&(1<<(i&31))) // p is prime
        for (j=(pp-3)/2; j<h; j+=p) sv[j>>5]&=(~(1<<(j&31))); // SetFalse
  return sv; // 2 non inclus
}

int main() { // SieveC
  clock_t t;
  u32 i, m, n, *sv;

  printf("SieveC (Crible d'Eratosthene):");
  for (m=10; m<=1000000000; m*=10) {
    t=GetTickCount();
    sv=Sieve(m);
    t=GetTickCount()-t;
    for (i=0, n=1; i<(m-1)/2; i++)
      if (sv[i>>5]&(1<<(i&31))) n++; // nombre de premiers
    free(sv);
    printf("nm=%d, n=%d, t=%d ms", m , n, t);
  }
  getchar();
}

Temps d'exécution:
m=10, n=4, t=0 ms
m=100, n=25, t=0 ms
m=1000, n=168, t=0 ms
m=10000, n=1229, t=0 ms
m=100000, n=9592, t=0 ms
m=1000000, n=78498, t=0 ms
m=10000000, n=664579, t=16 ms
m=100000000, n=5761455, t=312 ms
m=1000000000, n=50847534, t=4696 ms

Bonne surprise: malgré que l'instruction de la boucle intérieure semble plus compliquée, le temps de calcul s'est amélioré !!!
Le code "Simulation d'un BitSet32" ci-dessus à l'air d'être performant, surtout utilisé "inline"!
Ou est-ce le compilateur qui gère pas très bien les "array of bool" ?

L'utilisation de mots de 64 bits (unsigned _int64) donne des résultats moins bons car le compilateur a l'air d'être (encore) basé sur 32 bits.

Je suis entrain de finir l'article "Nombres premiers: Crible avec cycle additif" dans Javascript, qui, basé sur le crible d'Eratosthène, "élimine d'avance" non seulement les nombres multiples de 2 (pairs), mais aussi les multiples des nombres premiers suivants.
Il sera également suivi d'un article (dans C/C++) avec quelques "optimisations".
 
 
Accédez aux tests et sources de tous mes travaux sur les nombres premiers: ICI (sous Maths, Nombres premiers).
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)