Nombres premiers: le crible d'Eratosthène binaire

Télécharger le projet
Commenter

Description

Bonjour,

Ce complément à l'article "Le crible d'Eratosthène classique" présente quelques méthodes de se servir que d'un seul bit par élément du crible.
L'avantage principal est le gain de place mémoire utilisée.
Qu'en est-il en ce qui concerne le temps d'exécution ?

Différentes options sont traitées et mesurées:

vector(bool):
manipulations du bit:
a) 8 bits dans un array "unsigned char"
b) 16 bits dans un array "unsigned short int"
c) 32 bits dans un array "unsigned int U32"
d) 64 bits dans un array "unsigned long long int"

Le crible classique: EratoD

Nous partons de la fonction EratoD de Le crible d'Eratosthène classique: 
bool *EratoD(U32 mx) {
  bool *isPrime=(bool*)malloc(mx+1);
  memset(isPrime,true,mx+1); isPrime[0]=false; isPrime[1]=false;

  for (U32 p=2; p*p<=mx; ++p)
    if (isPrime[p])
      for (U32 q=mx/p; q>=p; --q) if (isPrime[q]) isPrime[p*q]=false;

  return isPrime;
}
/*
EratoD:
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=3 ms
m=10000000, n=664579, t=42 ms
m=100000000, n=5761455, t=464 ms
m=1000000000, n=50847534, t=5364 ms
*/
Les temps de calcul mesurés sont un peu plus grands que ceux obtenus sous "Le crible d'Eratosthène classique".
Est-ce que le passage à Windows 10 peut expliquer cette différence ?

Le crible binaire: EratoBit

"Remplaçons" les booléens par des bits en utilisant les #typedef et les #define suivants: 
typedef unsigned char U8;
typedef unsigned short int U16;
typedef unsigned int U32;
typedef unsigned long long int U64;

#define B8get(u8,idx)  (u8[idx>>3] &   (1<<(idx&7)) )
#define B8set0(u8,idx) {u8[idx>>3] &= ~(1<<(idx&7));}
#define B16get(u16,idx)  (u16[idx>>4] &   (1<<(idx&15)) )
#define B16set0(u16,idx) {u16[idx>>4] &= ~(1<<(idx&15));}
#define B32get(u32,idx)  (u32[idx>>5] &   (1<<(idx&31)) )
#define B32set0(u32,idx) {u32[idx>>5] &= ~(1<<(idx&31));}
#define B64get(u64,idx)  (u64[idx>>6] &   (1ULL<<(idx&63)) )
#define B64set0(u64,idx) {u64[idx>>6] &= ~(1ULL<<(idx&63));}
Ces "#define" ont déjà été implicitement utilisés dans:
Nombres premiers: crible d'Eratosthène
Nombres premiers: crible des multiplications 

U8 *EratoBit(U32 mx) {
  U8 *bs=(U8*)malloc(1+mx/8);   // idx: 0 1 2 3 4 5 6 7 8 9 10 11 12 ...
  bs[0]=252; memset(bs+1,255,mx/8); // [0,0,1,1,1,1,1,1|1,1, 1, 1, 1,...] bits

  for (U32 p=2; p*p<=mx; ++p)
    if (B8get(bs,p))
      for (U32 q=mx/p; q>=p; --q) if (B8get(bs,q)) B8set0(bs,p*q);

  return bs;
}
/*
EratoBit:
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=4 ms
m=10000000, n=664579, t=53 ms
m=100000000, n=5761455, t=760 ms
m=1000000000, n=50847534, t=8507 ms
*/
Nous constatons qu'EratoBit est d'environs 50% plus lent que EratoD.

Le crible avec vector<bool>: EratoVec

Qu'en est-il de ce code en utilisant vector<bool>: 
std::vector<bool> EratoVec(U32 mx) {
  std::vector<bool> vbs(mx+1,true);
  vbs[0]=vbs[1]=false;

  for (U32 p=2; p*p<=mx; ++p)
    if (vbs[p])
      for (U32 q=mx/p; q>=p; --q) if (vbs[q]) vbs[p*q]=false;

  return vbs;
}
/*
EratoVec:
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=6 ms
m=10000000, n=664579, t=63 ms
m=100000000, n=5761455, t=973 ms
m=1000000000, n=50847534, t=10958 ms
*/
Malheureusement, EratoVec est encore plus lent, c'est-à-dire que son temps d'exécution correspond environ au double de celui de EratoD (qui utilise bool).

Cribles binaires améliorés

Comparons maintenant les différentes manière d'utiliser les bits dans des "mots" de 8, 16, 32 et 64 bits.
De plus, améliorons l'algorithme en neutralisant les éléments pairs (sauf 2) dans l'initialisation du crible. 
U8 *EratoBit8(U32 mx) {
  U8 *bs8=(U8*)malloc(1+mx/8);
  bs8[0]=0xAC; memset(bs8+1,0xAA,mx/8);

  for (U32 p=3; p*p<=mx; ++p)
    if (B8get(bs8,p))
      for (U32 q=mx/p; q>=p; --q) if (B8get(bs8,q)) B8set0(bs8,p*q);

  return bs8;
}
/*
EratoBit8:
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=3 ms
m=10000000, n=664579, t=37 ms
m=100000000, n=5761455, t=634 ms
m=1000000000, n=50847534, t=7573 ms
*/

U16 *EratoBit16(U32 mx) {
  U16 *bs16=(U16*)malloc(2*(1+mx/16));
  bs16[0]=0xAAAC;
  for (U32 n=1; n<=mx/16; ++n) bs16[n]=0xAAAA;

  for (U32 p=3; p*p<=mx; ++p)
    if (B16get(bs16,p))
      for (U32 q=mx/p; q>=p; --q) if (B16get(bs16,q)) B16set0(bs16,p*q);

  return bs16;
}
/*
EratoBit16:
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=3 ms
m=10000000, n=664579, t=42 ms
m=100000000, n=5761455, t=636 ms
m=1000000000, n=50847534, t=7580 ms
*/

U32 *EratoBit32(U32 mx) {
  U32 *bs32=(U32*)malloc(4*(1+mx/32));
  bs32[0]=0xAAAAAAAC;
  for (U32 n=1; n<=mx/32; ++n) bs32[n]=0xAAAAAAAA; // bits impairs

  for (U32 p=3; p*p<=mx; ++p)
    if (B32get(bs32,p))
      for (U32 q=mx/p; q>=p; --q) if (B32get(bs32,q)) B32set0(bs32,p*q);

  return bs32;
}
/*
EratoBit32:
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=4 ms
m=10000000, n=664579, t=39 ms
m=100000000, n=5761455, t=642 ms
m=1000000000, n=50847534, t=7547 ms
*/

U64 *EratoBit64(U32 mx) {
  U64 *bs64=(U64*)malloc(8*(1+mx/64));
  bs64[0]=0xAAAAAAAAAAAAAAAC;
  for (U32 n=1; n<=mx/64; ++n) bs64[n]=0xAAAAAAAAAAAAAAAA;

  for (U32 p=3; p*p<=mx; ++p)
    if (B64get(bs64,p))
      for (U32 q=mx/p; q>=p; --q) if (B64get(bs64,q)) B64set0(bs64,p*q);

  return bs64;
}
/*
EratoBit64:
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=3 ms
m=10000000, n=664579, t=42 ms
m=100000000, n=5761455, t=648 ms
m=1000000000, n=50847534, t=7542 ms
*/

Résumé

Pour créer un crible d'Eratosthène entre 0 et 10⁹ (un milliard), il faut:
1'000'000'001 octets et 5364 ms avec EratoD
125'000'001 octets et 8507 ms avec EratoBit
125'000'001 octets et 10958 ms avec EratoVec
125'000'001 octets et 7573 ms avec EratoBit8
125'000'002 octets et 7580 ms avec EratoBit16
125'000'004 octets et 7547 ms avec EratoBit32
125'000'008 octets et 7542 ms avec EratoBit64
(Mesures avec un processeur I5, 3.2 GHz, 64 bits)

On constate que:
a) EratoD reste le meilleur en temps d'exécution.
b) EratoD prend 8 fois plus de mémoire que les autres.
c) EratoVec est le plus lent.
d) Les différences des 4 cribles améliorés sont minimes.

Le zip contient un programme qui vous permet de tester tous ces codes sur votre propre ordinateur.
Merci de me signaler des différences intéressantes.

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)