- Modificato
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.