Nombres premiers: crible d'Eratosthène

Soyez le premier à donner votre avis sur cette source.

Vue 5 594 fois - Téléchargée 507 fois

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).

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

pgl10
Messages postés
312
Date d'inscription
samedi 18 décembre 2004
Statut
Membre
Dernière intervention
5 février 2020
1
Il y a un autre moyen de gagner un peu plus de temps d'exécution avec SieveC.
Dans un premier temps on marque les multiples impairs de 3 séparément.
De toutes façons, il faut bien les marquer dans cette méthode. Mais ensuite
non seulement il n'est plus nécessaire nécessaire de les examiner => p+=s
avec s : 2 ou 4 mais en plus il n'est plus nécessaire de marquer le multiples
de p qui sont aussi multiples de 3 => j+=t*p; avec t : 1 ou 2 Ce qui donne :
u32* Sieve(u32 mx) { // Utilisation bitset
  u32 i, j, p, pp, s, t, 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 (j=3; j<h; j+=3) sv[j>>5]&=(~(1<<(j&31)));  // les multiples impairs de 3
  s=4;
  for (p=5, pp=25; pp<=mx; p+=s, pp=p*p) {  // les multiples de 3 sont évités
    i=(p-3)/2;
    s=6-s;
    if (sv[i>>5]&(1<<(i&31))) { // p is prime
      if(((i+2)*i)%3) t=1; else t=2;
      for (j=(pp-3)/2; j<h; j+=t*p) {  // les multiples de 3 sont déjà marqués
        t=3-t;
        sv[j>>5]&=(~(1<<(j&31))); // SetFalse
      }
    }
  }
  return sv; // 2 non inclus
}
Chez moi cela gagne plus de 20% du temps d'exécution.
pgl10
Messages postés
312
Date d'inscription
samedi 18 décembre 2004
Statut
Membre
Dernière intervention
5 février 2020
1 > pgl10
Messages postés
312
Date d'inscription
samedi 18 décembre 2004
Statut
Membre
Dernière intervention
5 février 2020

Bonjour tous,
Pour répondre à :
Question: serait-il possible de la diminuer encore en éliminant d'avance également les multiples de 3 ? Et pourquoi pas aussi les multiples de 5, 7, 11, ... ?
j'ai programmé un crible d'Eratosthène dans lequel on évite les multiples de 2, 3, 5 et 7 dans le crible. On observe 1°) une réduction sensible de la taille du crible 2°) une petite réduction du temps de calcul du crible 3°) mais aussi une augmentation du temps de parcours du crible dans la phase suivante où on compte les nombres premiers. En effet dans cette seconde phase il faut vérifier si chaque nombre candidat est un multiple de 2, 3, 5 ou 7 avant d'utiliser le crible, ce qui ralentit considérablement cette étape. En résumé cette méthode est intéressante quand on veut absolument diminuer la mémoire utilisée ou quand on veut utiliser le crible pour quelques nombres et pas pour tous.
William VOIROL
Messages postés
261
Date d'inscription
mardi 12 décembre 2006
Statut
Membre
Dernière intervention
10 juin 2019
> pgl10
Messages postés
312
Date d'inscription
samedi 18 décembre 2004
Statut
Membre
Dernière intervention
5 février 2020

J'aimerais remercier ceux qui participent activement et positivement à l'amélioration des codes proposés. Un gain de 20% du temps d'exécution est remarquable !

En épurant d'avance le crible des nombres pairs, on a pu diviser la mémoire utilisée en deux. Question: serait-il possible de la diminuer encore en éliminant d'avance également les multiples de 3 ? Et pourquoi pas aussi les multiples de 5, 7, 11, ... ?
Cette "généralisation" correspond à l'article "Nombres premiers: Crible avec cycle additif" que j'essaye de terminer prochainement.

Le fait d'avoir écrit xyz>>5 à la place de xyz/32 semble avoir dissimulé une qualité essentielle du code SieveC: l'optimisation maximale de la mémoire en n'utilisant qu'un seul "bit" par élément du crible (déjà restreint aux nombres impairs).
En effet, pour mx=1'000'000'000 par exemple, on alloue 500'000'000 "bits" ou 62'500'000 "bytes (char)" ou 15'625'000 "u32". SieveC passe donc de 500 Mo à 62.5 Mo (division par 8 par rapport à SieveB, comme mentionné) tout en améliorant le temps d'exécution !!!

Pour simuler un grand tableau de "bits" (valeurs vrai-faux ou 0-1), il est souvent conseillé de se baser sur les 8 bits d'un char (ou unsigned char). Après quelques mesures, j'ai constaté une amélioration de quelques % en me basant plutôt les 32 bits d'un unsigned _int32 (u32).

Pour essayer de "situer" le code SieveC par rapport à d'autres qui permettent également de déterminer le crible d'Eratosthène avec une valeur maximale mx <= 4'294'709'602 (correspond à 203'268'793 nombres premiers), je donne ici quelques mesures (même ordinateur et compilateur):

année, temps d'exec., 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], SieveC

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

Voir également: Nombres premiers.
pgl10
Messages postés
312
Date d'inscription
samedi 18 décembre 2004
Statut
Membre
Dernière intervention
5 février 2020
1
Bonjour à tous,
La comparaison de plusieurs méthodes pour résoudre le même problème est un avantage très intéressant.
A titre d'amusement on peut programmer ici la variante suivante dans SieveC :
1°) déclarer au début de u32* Sieve(u32 mx) { ... } :
u32 z[32] = {
0xFFFFFFFE, 0xFFFFFFFD, 0xFFFFFFFB, 0xFFFFFFF7, 0xFFFFFFEF, 0xFFFFFFDF, 0xFFFFFFBF, 0xFFFFFF7F,
0xFFFFFEFF, 0xFFFFFDFF, 0xFFFFFBFF, 0xFFFFF7FF, 0xFFFFEFFF, 0xFFFFDFFF, 0xFFFFBFFF, 0xFFFF7FFF,
0xFFFEFFFF, 0xFFFDFFFF, 0xFFFBFFFF, 0xFFF7FFFF, 0xFFEFFFFF, 0xFFDFFFFF, 0xFFBFFFFF, 0xFF7FFFFF,
0xFEFFFFFF, 0xFDFFFFFF, 0xFBFFFFFF, 0xF7FFFFFF, 0xEFFFFFFF, 0xDFFFFFFF, 0xBFFFFFFF, 0x7FFFFFFF};
2°) alors on peut, si on le veut, remplacer : sv[j>>5]&=(~(1<<(j&31)));
par : sv[j>>5]&=z[j&31]; ( ou même : sv[j>>5]&=z[j%32]; )
Cela effectue la même action, cela fait un calcul plus simple mais au prix d'un chargement mémoire en plus.
Chez moi cela gagne quelques petits pourcentages en temps d'exécution. Ce n'est donc pas significatif.
A chacun son choix !
KX
Messages postés
16141
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
30 mars 2020
92
En vrac :

"J'y remplace simplement le type char par bool"
Quel intérêt ? char et bool font tous les deux 1 octet...

"Essayons d'utiliser la notion de "pointeur", dans le but de remplacer dans la boucle intérieure sv[j]=false par *s=false"
Là encore, pourquoi ? sv[j] c'est la même chose que *s+j, donc une fois compilé ces deux syntaxes différentes sont en fait strictement équivalentes en assembleur.

"L'amélioration n'est pas flagrante"
Bah non, c'est normal...

"à l'air d'être performant, surtout utilisé "inline""
Les appels aux fonctions sont coûteux, ça fait des allers-retours dans la mémoire, ça copie les valeurs dans les paramètre, ça copie le résultat...
Là encore c'est normal que ce soit meilleur "inline".


Je pense qu'il vaux mieux te concentrer sur les améliorations algorithmiques que structurelles des langages, ou alors passes directement à l'assembleur...
Tu parlais de la crible d'Atkin c'est une vraie idée d'amélioration.

Mais l'intérêt de lister les petits nombres premiers (les premiers milliards on les connaît déjà) est assez limité. Il est plus intéressant (surtout en cryptographie) de s'intéresser aux nombres premiers très grands (ordre de grandeur 10^100 ~ 10^1000).

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.