Salve, stavo leggendo su un sito l'illustrazione di due tipi di algoritmi per cercare numeri primi;
il primo è molto semplice ed intuitivo, segue la definizione di numero primo (cioè un numero divisibile solo per se stesso) ed aveva questa impostazione (questo è una mia versione del codice perchè l'originale non funzionava per un errore, ma è lo stesso algoritmo a meno di nomenclature e ordine):
#include<stdio.h>
//Funzione di controllo
long long int controllo(long long int lim){
int i;
for(i=2;i<lim;i++)
if(lim%i == 0)
return 0;
return 1;
}
int main(){
long long int i, lim, primo = 0;
printf("\tCalcolo numeri primi\n");
printf("\nInserire il limite superiore per la ricerca: ");
scanf("%lld",&lim);
//Calcoli
for(i=0;i<=lim;i++){
if(controllo(i))
printf("%lld\n\n",i);
}
system("PAUSE");
return 0;
}
Quindi opera un confronto con un altro algoritmo, basato sul primo, ma che usa un'altra sfaccettatura della definizione dei numeri primi, e cioè che per controllare se un numero è primo o no basta verificare che non sia divisibile solo per i primi più piccoli del numero da controllare. Cosa che facilita di molto il calcolo, ma a quanto pare non lo velocizza
Il codice è questo:
#include<stdio.h>
#include<stdlib.h>
long long int *primi,ii=2;
long long int primo(long long int num);
int main(){
long long int i, numeri;
primi = (long long int*)malloc(sizeof(long long int));
primi[0] = 2;
printf("\tCalcolo numeri primi\n");
printf("\nInserisci il numero fino al quale vuoi arrivare: ");
scanf("%lld",&numeri);
for(i = 2; i<=numeri; i++){
if(primo(i)){
printf("\n%lld\n\n",i);
}
}
//printf("\nDati salvati sul file di log.\n\n");
system("PAUSE");
return 0;
}
//Funzione di controllo
long long int primo(long long int num){
primi = (long long int*)realloc(primi,sizeof(long long int)*ii);
long long int i;
long long int prim = 1;
if(num == 2)
return 1;
for(i=0;i<ii-1;i++)
if(num%primi[i] == 0)
prim = 0;
if (prim)
primi[ii++-1] = num;
return prim;
}
L'autore del post dice che il secondo codice, rispetto al primo, impiega molto meno tempo a trovare i numeri (e lui cita un range fino a 10000 numeri, che non sono neanche tanti per testarne le prestazioni).
Facendo la prova, se si eseguono i codici cosi come sono appare evidente dall'output che il secondo è molto più lento in realtà, addirittura aprendo due finestre del terminale e facendo partire prima quello con "l'ottimizzazione" e poi quello di base, quello di base lo supera subito e l'altro rimane indietro tantissimo, addirittura nell'oridine di 10^5 dopo qualche ora sui numeri trovati.
Ora io, a parte dei dubbi su come è scritto il secondo codice, che non capisco quando avviene il realloc del vettore e l'uso della variabile "ii", mi sono dato delle possibili spiegazioni (se funziona come si afferma e che non capisco):
1)la mia versione rispetto a quello ottimizzato ha solo bisogno di tempo per bloccarsi; cioè che da un certo valore in poi il ciclo for del primo codice sarà cosi sovraccarico che il secondo codice risulterà più veloce, ma verificando la cosa risulta poco attendibile perchè lasciandoli andare tutta la notte alla fine la versione di base è sempre la più veloce e soprattutto ha trovato un sacco di numeri in più rispetto all'altro, che invece rallenta molto più velocemente rispetto alla mia versione, quindi oltre ad essere in svantaggio sui primi trovati si trova anche in una condizione di divergenza sui tempi rispetto alla versione di base.
2) il realloc uccide la memoria (e fin qua sarebbe poco male con le ram odierne), impiegando anche un sacco di cicli ad eseguire il realloco della memoria, al punto che la quantità di cicli del clock per eseguire il for su un numero grande è una frazione rispetto a quelli necessari per eseguire il realloc (frazione molto piccola osservando gli output), cosa che non ho verificato perchè dovrei disassemblare il codice con la libreria stdlib implementata e vedere il codice in asm com'è, anche se sò per sentito dice che dal punto di vista dell'assembly le librerie del C sono poco ottimizzate con istruzioni della serie MOV EDI, EDI ecc.. che fanno perdere un sacco di tempo e potrebbero essere rimpiazzate da dei NOP (ma il punto non è questo).
Il punto è spiegarsi questa differenza, ma soprattutto perchè l'autore del post dove ho trovato quell'algoritmo dice che il secondo codice è più veloce quando, facendo un test, si vede che non è cosi.
Voi riscontrate problemi magari nel sorgente? E come potrebbero essere risolti?
P.S. i codici sono stati eseguiti su macchine diverse con linux e windows, compilati sempre con GCC e producono lo stesso output.