Nombres premiers bis

Télécharger le projet
Commenter

Description

En regardant de plus près l'algorithme utilisé dans la fonction 'prems' de pgl10, et après quelques "impressions intermédiaires", j'ai remarqué que la mémoire auxiliaire initialisée est beaucoup plus grande que celle effectivement utilisée.
L'output "ImpressionsIntermediaires.txt" du programme "ImpressionsIntermediaires.cpp" (dans le Zip), et le tableau suivant:
   i-Max = 100, k-Max = 10
   i-Max = 1000, k-Max = 24
   i-Max = 10000, k-Max = 67
   i-Max = 100000, k-Max = 190
   i-Max = 1000000, k-Max = 547
   i-Max = 10000000, k-Max = 1588
le montrent clairement.

On peut donc limiter la taille de la mémoire auxiliaire mp, par exemple à la racine carrée du nombre de nombres premiers demandé.
Voici une adaptation: 
int prems(int nnp, int* np) { // par pgl10, adapté par William VOIROL
    const int maxi = INT_MAX, ieme = 105097565;
    int i=5,m,n,s=0,t[]={4,2,4,2,4,6,2,6},len,*mp;
    if(nnp<ieme) m = nnp+1; else m = ieme;
    len = (m < 100) ? 10 : 1+int32_t(sqrt(m));
    mp = new int[len];
    np[0]=1;  np[1]=2;  np[2]=3;  np[3]=5;    np[4]=7;
    mp[0]=1;  mp[1]=4;  mp[2]=9;  mp[3]=5*5;  mp[4]=7*7;
    for(n=11; i<m; n=n+t[s]) {  // 11 13 17 19 23 29 31 37 41 43 47 49 ...
        for(int k=4;;k++) {
            int j = np[k];
            if( n == mp[k] ) break; // Si n est multiple de np[k]
            if( int64_t(j)*j > int64_t(n) ) { // Si aucun np[k] n'a fourni
                np[i++] = n;                  // un diviseur de n, alors
                mp[++k]=np[k]*np[k];
                break;
            }
            if( n > mp[k] ) mp[k] += 2*j;
        }                                     
        if(++s == 8) s=0;
    }
    delete[] mp;   // libérer la mémoire du tableau auxiliaire mp[]
    if(nnp == ieme) np[ieme] = maxi;
    return len;
}
Ce code semble également un peu plus rapide.

Pour une limitation plus précise, on pourrait utiliser <vector> pour définir mp.

De plus, en passant à des unsigned int, il serait possible de presque doubler les capacités de la fonction.
 

PrimeListBin

Divisons la mémoire auxiliaire utilisée (pour le crible d'Eratosthène) par 8 en utilisant des bits à la place de unsigned char pour définir l'array usv de la fonction PrimeList.

En nous référant à:
   ► CodeS-SourceS: Nombres premiers: le crible d'Eratosthène binaire,
utilisons
   #define B8get(u8,idx) (u8[(idx)>>3] & (1<<((idx)&7)) )
   #define B8set0(u8,idx) {u8[(idx)>>3] &= ~(1<<((idx)&7));}
pour les opération binaires nécessaires: 
#define B8get(u8,idx)  (u8[(idx)>>3] &   (1<<((idx)&7)) )
#define B8set0(u8,idx) {u8[(idx)>>3] &= ~(1<<((idx)&7));}

unsigned int PrimeListBin(unsigned int N,unsigned int *np) { // array of primes <= N
  unsigned int E=(N+1)/2, M=(E+7)/8, m=E;
  unsigned char *usv=new unsigned char[M];
  memset(usv,255,M);
  for (unsigned int i=1,e=3; e<=N; ++i,e+=2)
    if (B8get(usv,i))
      for (unsigned int j=(N/e-1)/2; j>=i; --j)
        if (B8get(usv,j)) {B8set0(usv,i+e*j); --m;}
  np[0]=2;
  for (unsigned int e=1,k=1; e<E; ++e)
    if (B8get(usv,e)) np[k++]=(e<<1)|1;
  delete[] usv;
  return m;
}
C'est avec plaisir que je constate que le temps d'execution n'est augmenté que d'environ 15% !

Testez vous-mêmes les résultats suivants en exécutant ListeBis.cpp du Zip: 
prems:
lst[10]=29, 44 oct, 0 ms
lst[100]=541, 44 oct, 0 ms
lst[1000]=7919, 124 oct, 0 ms
lst[10000]=104729, 400 oct, 1 ms
lst[100000]=1299709, 1264 oct, 28 ms
lst[1000000]=15485863, 4000 oct, 601 ms
lst[10000000]=179424673, 12648 oct, 14795 ms

PrimeList:
lst[9]=29, 15 oct, 0 ms
lst[99]=541, 271 oct, 0 ms
lst[999]=7919, 3960 oct, 0 ms
lst[9999]=104729, 52365 oct, 0 ms
lst[99999]=1299709, 649855 oct, 6 ms
lst[999999]=15485863, 7742932 oct, 78 ms
lst[9999999]=179424673, 89712337 oct, 940 ms

PrimeListBin:
lst[9]=29, 2 oct, 0 ms
lst[99]=541, 34 oct, 0 ms
lst[999]=7919, 495 oct, 0 ms
lst[9999]=104729, 6546 oct, 0 ms
lst[99999]=1299709, 81232 oct, 6 ms
lst[999999]=15485863, 967867 oct, 78 ms
lst[9999999]=179424673, 11214043 oct, 1095 ms

 
Bonne lecture ...
 

Liens

CodeS-SourceS: Nombres premiers
CodeS-SourceS-pgl10: Nombres premiers
CodeS-SourceS: Nombres premiers: essais de division avec liste
CodeS-SourceS: Nombres premiers: PrimeList
CodeS-SourceS: Nombres premiers: le crible d'Eratosthène binaire
 
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)