Nombres premiers: crible des multiplications

Télécharger le projet
Commenter

Description


Nombres premiers: crible des multiplications


Le principe de l'algorithme consiste à parcourir la table de multiplication pour neutraliser dans le crible (sv) chaque élément qui correspondant à un produit.
Vous trouverez la description originale sous Nombres premiers: crible des multiplications.
Comme Javascript est loin d'être performant, je présente ici une "optimisation en C" de quelques codes.
 
Une version actualisée de l'introduction aux nombres premiers, complétée de mesures des temps d'exécution, peut être obtenue ici Nombres premiers.
Autres liens sur les nombres premiers:
Essais de division
Essais de division avec liste
Crible d'Eratosthène
Crible d'Eratosthène (optimisation C)
Crible d'Atkin

Remarque: Les codes qui suivent ne font que "remplir" le crible et utilisent:
typedef unsigned _int32 u32;
 
 

MultA.cpp


Traduisons d'abord du code Javascript Mult7.js en C et ajoutons un "main()" pour le tester: 
 
bool *Mult(u32 mx, u32 &h) { // MultA "Crible des produits": mx > 9 
  u32 a=(mx-5)%6,d,j,k,u,v,xy[2]; 
  h=((mx-5-a)/3+((a>1)?4:3)); // nombre de bits significatifs du crible 
  bool *sv=(bool*)malloc(h*sizeof(bool)); 
  for (k=0; k<h; k++) sv[k]=true; 
  for (j=2,d=9,u=0,v=8; d<h; d+=(++j&1)? u+=8: v+=16) 
    if (sv[j]) { 
      if (j&1) {xy[0]=2*j-1; xy[1]=4*j-3;} else {xy[0]=4*j-1; xy[1]=2*j-1;} 
      for (k=d; k<h; k+=xy[k&1]) sv[k]=false; 
    } 
  return sv; 
} // William Voirol, Switzerland

Temps d'exécution (fichier MultA.cpp):

MultA (Crible des produits):
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=390 ms
m=1000000000, n=50847534, t=4804 ms

On peut extraire du crible la liste des nombres premiers p (à partir de 5) avec la boucle
for (i=2,p=5; i<h; p+=cyc[i&1],i++) if (sv[i]) { /* p is prime */ }
 
 

MultB.cpp


Puis optimisons la mémoire en n'utilisant qu'un seul bit par élément du crible.
Après quelques mesures, j'ai constaté une amélioration de quelques % du temps d'exécution en utilisant les 32 bits d'un unsigned _int32 plutôt que les 8 bits d'un unsigned char, comme souvent conseillé. 
 
u32 *Mult(u32 mx, u32 &h) { // MultB "Crible des produits": mx > 9 
  u32 a=(mx-5)%6,d,j,k,n,u,v,xy[2]; 
  h=((mx-5-a)/3+((a>1)?4:3)); // nombre de bits significatifs du crible 
  u32 *sv=(u32*)malloc((n=(h+31)/32)*sizeof(u32)); // 8 bits par byte => 32 bits par u32 
  for (j=0; j<n; j++) sv[j]=0XFFFFFFFF; // All true 
  for (j=2,d=9,u=0,v=8; d<h; d+=(++j&1)? u+=8: v+=16) 
    if (sv[j>>5]&(1<<(j&31))) { 
      if (j&1) {xy[0]=(j<<1)-1; xy[1]=(j<<2)-3;} else {xy[0]=(j<<2)-1; xy[1]=(j<<1)-1;} 
      for (k=d; k<h; k+=xy[k&1]) sv[k>>5]&=(~(1<<(k&31))); // SetFalse 
    } 
  return sv; 
} // William Voirol, Switzerland

Temps d'exécution (fichier MultB.cpp):

MultB (Crible des produits):
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=15 ms
m=100000000, n=5761455, t=171 ms
m=1000000000, n=50847534, t=3650 ms

Surprise, nous gagnons sur les deux tableaux: mémoire utilisée et temps d'éxecution !!!

On peut extraire du crible la liste des nombres premiers p (à partir de 5) avec la boucle
for (i=2,p=5; i<h; p+=cyc[i&1],i++) if (sv[i>>5]&(1<<(i&31))) { /* p is prime */ }
 
 
Pour essayer de situer le dernier code MultB par rapport à d'autres qui permettent également de déterminer le crible d'Eratosthène avec une valeur maximale mx <= 4'294'709'602 (correspondant à 203'268'793 nombres premiers), je donne quelques mesures (même ordinateur et compilateur):

(année, temps d'exéc., mémoire, lien):
2003, 53.461 s, bit[Max/2], 1 000 000 de nombres premiers en 0.062 secondes
2011, 63.773 s, bit[Max/2], crible d'eratosthène optimisé
2013, 23.167 s, bit[Max/2], Nombres premiers: crible d'Eratosthène
2013, 17.659 s, bit[Max/3], MultB (fichier MultB-Max.cpp)

Aidez-moi à améliorer, compléter ou corriger cette liste.

Voir aussi 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)