Nombres premiers: Crible segmenté (D)

Télécharger le projet
Commenter

Description

Bonjour,

Les cribles des codes de Wallisch et également PrimeToSieve et PrimeToSegSieve contiennent les nombres pairs alors qu'ils sont ignorés.

En les éliminant complètement, l'efficience est améliorée et la place mémoire utilisée est divisée par deux.

Crible impair (OddSieve)

Un crible impair peut être structuré de la manière suivante: 
// Crible impair (OddSieve): nombres pairs absents (sauf 2)
// correspondance:  i=e/2;  e=2*i+1; (sauf si i=0: e=2)
// i: 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 ...
// e: 2  3  5  7  9 11 13 15 17 19 21 23 25 27 29 31 33 35 ...
// p: 2  3  5  7  - 11 13 -- 17 19 -- 23 -- -- 29 31 -- -- ...
Cette structure a déjà été présentée et est utilisée dans PrimList et PrimesToOddSieve.

PrimesToSegOddSieve

Les adaptations pour passer de PrimesToSegSieve à PrimesToSegOddSieve sont minimes: 
typedef unsigned char uchar;
typedef unsigned int uint;

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

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

uint PrimesToSegOddSieve(uint NN) {
  uint n=0, ni=0, M=(NN+1)/2;
  for (uint A=0, B, R, E; A<M; A=B) { // B, E not included
    B=(A+SS<M)?A+SS:M, R=(uint)sqrt(B+B-1);
    memset(seg, 1, E=B-A);
    for (uint i=1, p=3, e; p<=R; p=lst[++i]) {
      if (i>ni) idx[++ni]=e=p*p/2-A; else e=idx[i];
      for (; e<E; e+=p) seg[e]=0;
      idx[i]=e-SS;
    }
    for (uint e=0; e<E; ++e) n+=seg[e];
  }
  return n;
} // by William VOIROL, Switzerland, Jan 2017

Comme dans Nombres premiers: Crible segmenté (B), la rapidité s'améliore d'environ 20% par rapport à PrimesToSegSieve: 
PrimesToSegOddSieve, 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, 0 ms
664579/10000000, 8 ms
5761455/100000000, 87 ms
50847534/1000000000, 1005 ms

203268793/4294709602, 4930 ms

Code original Wallisch (même ordi):

50847534/1000000000, 2005 ms

203268793/4294709602, 10862 ms
PrimesToSegOddSieve va environ deux fois plus vite que le code original de Wallisch.

Je vais mettre à jour la liste Nombres premiers), car ces temps sont encore meilleurs que ceux obtenus avec PrimesToSegSieve.

Le code de la segmentation PrimesToSegOddEffSieve, correspondant à EratoOdd (voir: CodeS-SourceS: Le crible d'Eratosthène classique) sera un peu plus compliqué, car on y parcourt le crible "à l'envers".

Et il y aura aussi d'autres "optimisations" telles que:
- utiliser un seul bit par élément du crible.
- épurer le crible initial d'autres multiples de petits nombres premiers (voir cycle additif).

Liens:
CodeS-SourceS: Nombres premiers: Crible segmenté (A)
CodeS-SourceS: Nombres premiers: Crible segmenté (B)
CodeS-SourceS: Nombres premiers: Crible segmenté (C)
CodeS-SourceS: Nombres premiers: Crible avec cycle additif
CodeS-SourceS: Nombres premiers: Crible avec cycle additif Bis
Kim Walisch: Segmented sieve of Eratosthenes

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)