Nombres premiers: Crible segmenté (C)

Télécharger le projet
Commenter

Description

Bonjour,

Comme promis, voici la segmentation de PrimesToSieve qui sera le code le plus rapide de ceux que j'ai développés ou adaptés jusqu'à maintenant.

Le code présenté devrait faire les mêmes opérations sur le crible (et dans le même ordre) que celui de Wallisch.

L'unique segment de 32768 octets est donné par la variable globale seg.

La liste lst des nombres premiers nécessaires est précalculée avec PrimeList donné dans PrimeList.cpp.
(voir CodeS-SourceS: Nombres premiers: PrimeList).

PrimesToSegSieve

Dans le code de Wallisch, les deux listes std::vector<int>primes et std::vector<int>next sont continuellement entretenues.
Comme on dispose déjà de la liste des nombres premiers, il suffit de maintenir idx, la liste des index de départ dans le segment: 
typedef unsigned char uchar;
typedef unsigned int uint;

uint *PrimeList(uint N, uint *NP); // voir PrimeList.cpp

const uint SS=32768; // SS must bee even (pair)
uchar *seg=(uchar*)malloc(SS); // segment of 32768 bytes
uint np, *lst=PrimeList(65535, &np), *idx=(uint*)malloc(4*np);

uint PrimesToSegSieve(uint NN) {
  uint n=0, ni=0;
  for (uint A=0, B, E; A<=NN; A=B) { // B, E not included
    B=(A+SS<=NN)?A+SS:NN+1;
    memset(seg, 1, E=B-A); // les éléments pairs sont présents, mais ignorés
    for (uint i=1, p=3, pp=9, e; pp<B; p=lst[++i], pp=p*p) {
      if (i>ni) idx[++ni]=e=pp-A; else e=idx[i];
      for (uint p2=p<<1; e<E; e+=p2) seg[e]=0;
      idx[i]=e-SS;
    }
    for (uint e=1; e<E; e+=2) n+=seg[e];
  }
  return n;
} // by William VOIROL, Switzerland, Jan 2017

L'exécution de PrimesToSegSieve.cpp donne: 
PrimesToSegSieve, seg-size=32768:

4/10, 0 ms
25/100, 0 ms
168/1000, 0 ms
1229/10000, 0 ms
9592/100000, 0 ms
78498/1000000, 1 ms
664579/10000000, 8 ms
5761455/100000000, 96 ms
50847534/1000000000, 1182 ms

203268793/4294709602, 6429 ms

Code original Wallisch (même ordi):

50847534/1000000000, 2005 ms

203268793/4294709602, 10862 ms


Ces temps sont meilleurs que ceux que j'ai obtenus jusqu'à présent (voir: Nombres premiers).
C'est donc avec plaisir que je vais mettre à jour cette liste.

La prochaine étape sera de segmenter PrimesToOddSieve, qui devrait, selon "Crible segmenté (B)", apporter une amélioration d'environ 20 %.

Liens:
CodeS-SourceS: Nombres premiers: Crible segmenté (A)
CodeS-SourceS: Nombres premiers: Crible segmenté (B)
CodeS-SourceS: Le crible d'Eratosthène classique
Kim Walisch: Segmented sieve of Eratosthenes
Kim Walisch: segmented_sieve.cpp

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)