• Programmazione
  • Calcolo lista numeri primi fino ad N: algoritmo più efficiente in C

Dopo alcune ispirazioni con particolare focus alle performance, come ad esempio il contest Project Euler - Longest Collatz Sequence (n.14), da cui la scelta più sensata ovviamente ricade sul linguaggio C, ho pensato ad un altro algoritmo interessante ovvero: creare la lista di numeri primi fino ad N, nel modo più efficiente possibile!

Alcune considerazioni importanti, spiegando le varie ottimizzazioni sia dal punto di vista informatico, sia matematico:

  • scelta del linguaggio C, salvare le variabili nei registri della CPU anziché nella memoria centrale (RAM), in modo tale da avere le massime performance, ridurre al minimo il tempo di accesso
  • ottimizzazione matematica: il massimo divisore possibile di un numero N è sqrt(N); spesso non si pensa a questo aspetto e vengono calcolate un'infinità di operazioni inutili e questo spreco cresce quadraticamente con il numero N! Infatti negli algoritmi tradizionali, in modo "semplice ma ingenuo" si calcolano i divisori da 2 fino a N oppure fino a (int)(N/2). Noto che ci si potrebbe fermare a sqrt(N), vediamo cosa comporta in termini di numero di operazioni:
    • N=10000: N/2=5000, sqrt(N)=100 ovvero 100 volte inferiore
    • N=1012: N/2=5*(1011), sqrt(N)=106, ovvero un milione di volte inferiore
    • e così via... Spero renda già l'idea! 😉

Riportiamo dunque il codice C, che salva la lista di numeri primi fino ad un valore pari a "MAXITER" (ad esempio in questo caso, i numeri primi da memorizzare saranno 1000 dato che ho impostato MAXITER=1000, ovviamente possiamo mettere il valore desiderato). Infine come output non stampo tutto l'array ma solo il valore finale e il numero totale di elementi in lista (per stampare tutta la lista, a video o su file, sarebbe sufficiente un ciclo, comunque la lista resta tutta memorizzata nell'array V[] quindi la si può gestire come si vuole). Riporto anche il tempo di esecuzione del codice.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

int main(){
register unsigned int cont=1;
register unsigned int MAXITER=1000;
register long int j=3;
register long int i=2;
register long int k;
long int V[MAXITER];
V[0]=2;
clock_t start = clock();
//creazione array di numeri primi
while(cont<MAXITER){
for(i=2;i<(int)(pow(j,0.5));i++){
if(j%i==0){break;}
}
if(j%i!=0){V[cont]=j;cont++;}
j++;
}
clock_t end = clock();
printf("%f s\n",(float)(end-start)/CLOCKS_PER_SEC);
printf("MAXITER=%d\nV[end]=%ld\n",MAXITER,V[MAXITER-1]);
return 0;
}

Risultati: il tempo di esecuzione è pari a 0.006218 s. Mettendo MAXITER=10000, il tempo di esecuzione diventa 0.134 s. Possiamo dunque considerarlo un algoritmo estremamente efficiente!

Giusto un confronto: con MAXITER=1000, se avessimo imposto il calcolo fino a (int)(j/2) anziché (int)(sqrt(j)), il tempo di esecuzione sarebbe stato 0.026 s ovvero 4 volte superiore. Con MAXITER=100000 sarebbe stato 2,44s ovvero 18 volte superiore! E così via, con andamento quadratico!! Da qui si vede l'importanza di aver definito un algoritmo super efficiente.

Come calcolare numeri primi partendo già da un valore noto?

Supponiamo questa situazione: sono già stati calcolati N numeri primi, ad esempio i primi 100.000 numeri primi, quindi con un determinato tempo di esecuzione. Ricordiamo ad esempio che f(105)=1.299.709.

Se volessi calcolare la lista fino al 300.000 numero primo, o meglio, vorrei conoscere il numero primo 300.000° in lista, sarebbe uno spreco di tempo e risorse calcolarli nuovamente tutti da zero! Quindi si può procedere in questo modo:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

int main(){
register unsigned int cont=1;
register unsigned int MAXITER=200002;
register long int j=1299709;
register long int i=2;
register long int k;
long int V[MAXITER];
V[0]=1299709;
clock_t start = clock();
//creazione array di numeri primi
while(cont<MAXITER){
for(i=2;i<(int)(pow(j,0.5));i++){
if(j%i==0){break;}
}
if(j%i!=0){V[cont]=j;cont++;}
j++;
}
clock_t end = clock();
printf("%f s\n",(float)(end-start)/CLOCKS_PER_SEC);
printf("MAXITER=%d\nV[end]=%ld\n",MAXITER,V[MAXITER-1]);
return 0;
}

Vediamo meglio il codice:

  • MAXITER 200002, significa 200.000 oltre il valore di partenza (100.000 in questo caso), +2 che aggiunto qui (infatti nel codice originale l'avevamo aggiunto a j che partiva da 3 anziché da 1, questa scelta insomma è arbitraria, una convenzione che per comodità ho scelto così)
  • j=1299709 ovvero il valore noto di partenza: il numero primo numero 105 è pari a questo valore
  • V[0]=1299709 ha senso scriverlo se poi ci interessa tutta la lista, se invece ci interessa solo la stampa a video del valore finale, questo non occorre

NB: ovviamente attenzione poi agli indici! Ad esempio V[0] si intende che lo zero sarebbe il numero di partenza, quindi ad esempio non zero bensì 100.000! Così come la funzione printf() che stampa a video i risultati, non l'ho corretta con gli indici aggiornati, insomma occorre saperlo! Se siamo partiti da zero fino a 105, l'ultimo valore dell'indice sarà 100.000-1, se invece siamo partiti da 100.000 fino a 300.000, sarà come detto prima nel punto relativo a MAXITER. Noi ovviamente sappiamo cosa stiamo calcolando quindi correggere gli indici non è indispensabile.

Risultati: eh sì, riportiamo la parte interessante, mica abbiamo fatto girare il codice per niente! 😃

  • 300.000° numero primo = 4.256.233
  • tempo di esecuzione del codice (partendo da 100.000): 17,9 secondi

E per quanto riguarda il milionesimo numero primo?

Ebbene, poi mi è venuta questa curiosità. Con un tempo di esecuzione pari a 115,6 secondi (partendo dal numero primo 300.000° in lista, calcolato prima), modificando il codice scritto prima ho voluto calcolare il milionesimo numero primo, dato che online non riesco a trovare scritto il suo valore. Ebbene, ve lo dico io: il milionesimo numero primo è 15485863.

Ecco un algoritmo ancora più efficiente!

Era opportuno pubblicare questo aggiornamento, ho trovato una strada ancora più efficiente. Per arrivare allo stesso risultato, il milionesimo numero primo (partendo daall'origine!), ho impiegato un tempo di esecuzione pari a:

  • 31,9 secondi, nel caso di variabili register unsigned long int
  • 14,1 secondi, nel caso di variabili register unsigned int

A seconda della previsione del numero finale, il consiglio per le performance è sempre quello ovviamente di assegnare la minor dimensione possibile alla variabile (quindi ad esempio int anziché long int, in modo che abbia appunto meno peso e l'algoritmo sia quindi più veloce nella gestione), così come salvarla forzatamente nei registri della CPU.

Ricordiamo che con l'algoritmo precedente il tempo di esecuzione a parità di condizioni era uguale a oltre 130 secondi. Quindi un miglioramento notevole!

Ecco riportato il codice per intero, si vede che in questo caso richiede una libreria in più. La compilazione da teminale sarà tramite questo comando: gcc nomefile.c -o nomefile -lm

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
#include <time.h>

bool f(unsigned int numero){
    double radice=sqrt(numero);
    bool verifica=true;
    for(int i=2;i<=radice;i++){
        if(numero%i==0){
            verifica=false;
            return verifica;
            break;
            }
    }
    return verifica;
}
int main(){
    register unsigned int numero=2;
    register unsigned int contatore=1;
clock_t start = clock();
    while(contatore<=1000000){
        if(f(numero))
            contatore++;
        numero++;
    }
clock_t end = clock();
//cout <<(float)(end-start)/CLOCKS_PER_SEC;
printf("%f s\n",(float)(end-start)/CLOCKS_PER_SEC);
printf("%d\n",numero-1);
return 0;
}

In conclusione, la ragione che sta dietro ad ogni aggiornamento, miglioramento può essere descritta dalla frase di Sir W. Churchill:

Non sempre cambiare equivale a migliorare, ma per migliorare bisogna cambiare

    Giulio_M Grandissimo, facendo un po' di ricerche ho trovato il Test di Miller-Rabin ricercato qui. Un algoritmo utile per verificare la primalità, mi ha aiutato molto anche questo articolo dove viene mostrata una vera applicazione.
    Per ottimizzare il tutto inoltre ho utilizzato uint64_t invece di unsigned int per aumentare la precisione.

    #include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    #include <math.h>
    #include <time.h>
    bool is_prime(unsigned int numero) {
    double radice = sqrt(numero);
    for (int i = 2; i <= radice; i++) {
    if (numero % i == 0) {
    return false;
    }
    }
    return true;
    }
    int main() {
    register unsigned int numero = 2;
    register unsigned int contatore = 1;
    clock_t start = clock();
    while (contatore <= 1000000) {
    if (is_prime(numero)) {
    contatore++;
    }
    numero++;
    }
    clock_t end = clock();
    printf("%f s\n", (float)(end - start) / CLOCKS_PER_SEC);
    printf("%d\n", numero - 1);
    return 0;
    }

    Per il test ho usato il compilatore online onlinegdb.

      Samueleex un ulteriore accorgimento che dimezza il numero delle iterazioni e quindi dimezza il tempo di esecuzione, che diventa 7,1 secondi (rispetto ai 14,1 secondi precedenti, stessa macchina ovviamente)!

      Concettualmente, facciamo questo: dopo aver provato la divisione per 2, a cosa serve verificare ogni numero pari? Se non è divisibile per 2 non lo sarà nemmeno per 4, per 6 e così via. Quindi verifichiamo numero%2 prima del ciclo e poi il ciclo si trasformerà in for (register int i = 3; i <=radice; i+=2). Ciò che cambia poi all'interno del main sarà while (contatore < N-1) (avendo fatto partire il contatore da 0 anziché da 1).

      In definitiva, questo è il codice completo con gli ultimi accorgimenti:

      #include <stdio.h>
      #include <stdbool.h>
      #include <math.h>
      #include <time.h>
      
      bool is_prime(unsigned int numero) {
      double radice = sqrt(numero);
      if(numero%2==0){return false;}
      for (register int i = 3; i <=radice; i+=2) {
      if (numero % i == 0) {
      return false;
      }
      }
      return true;
      }
      
      int main() {
      register unsigned int numero = 2;
      register unsigned int contatore = 0;
      register unsigned int N=1000000;
      clock_t start = clock();
      while (contatore < N-1) {
      if (is_prime(numero)) {
      contatore++;
      }
      numero++;
      }
      clock_t end = clock();
      printf("%f s\n", (float)(end - start) / CLOCKS_PER_SEC);
      printf("%d\n", numero - 1);
      return 0;
      }
      5 mesi dopo

      Aggiornamento: rispetto ai precedenti 7,1 secondi, a parità di macchina ovviamente, questa nuova ottimizzazione raggiunge 6,15 secondi! Quindi circa un 13% più efficiente di prima. Vediamo cosa è cambiato:

      • a livello concettuale (questo è indifferente per le performance), semplifichiamo: considerata la discussione Linguaggio C, variabili da 1 byte: benchmark (unsigned) char, bool e _Bool, di fatto in termini di performance è inutile includere la libreria <stdbool.h> per avere il dato bool, che di fatto per i nostri scopi è del tutto equivalente ad un char o unsigned char
      • al posto di double radice=sqrt(numero); scriviamo invece register unsigned int radice = sqrt(numero);. Più che sufficiente per il range e la gestione di una simile variabile, che dev'essere poi richiamata nel ciclo (essendo "numero" il quadrato di "radice", di fatto in termini di allocazione della memoria può limitarsi alla metà dei bit occupati dall'altra variabile, double); poi anche per la variabile "radice" forziamo l'uso del registro della CPU al posto della memoria centrale (RAM)

      Il codice modificato quindi riguarda la funzione is_prime(), ed è il seguente (come detto, avendo usato unsigend char, mettiamo 0 e 1 al posto dei testuali "true" e "false"):

      unsigned char is_prime(unsigned int numero) {
      register unsigned int radice = sqrt(numero); //migliore ottimizzazione finora!
      if(numero%2==0){return 0;}
      for (register unsigned int i = 3; i <=radice; i+=2) {
      if (numero % i == 0) {
      return 0;
      }
      }
      return 1;
      }

      Powered by: FreeFlarum.
      (remove this footer)