PDA

Visualizza la versione completa : [C] Minimizzare i tempi creazione numeri primi


JErikaM
01-07-2012, 18:23
Salve a tutti :)
Rieccomi, stavolta con un problema molto molto più irrilevante rispetto ai miei soliti :P
Sto implementando in un progetto , la creazione di numeri primi di grandi dimensioni, da 64 cifre l'uno..
Il mio codice funziona senza problemi, tuttavia i tempi di creazione sono lunghi (molto lunghi...) volevo quindi sapere se esistono modi per velocizzare una generazione di numeri primi quando si ha a che fare con numeri grandi.. (nel mio caso da 64 in su)
Qualche codice speciale...qualche funzione, non saprei...
tipo invece di fare un numero da 64 cifre se ne creano due da 32 e poi si assemblano in un unico vettore..ma non so 1) se sia facilmente fattibile 2) se c'è veramente risparmio di tempo...



bigInt bprimo(int dim)
{

bigInt primo, ris;
int i;
primo.sign = 0;
do
{
while(primo.num.size()>0) primo.num.pop_back();
for(i=0;i<dim-1;i++) primo.num.push_back(rand()%10);
primo.num.push_back(rand()%9);
if (primo.num[0]%2==0) printf("4");primo = bsub(primo,int2bint(1));
ris = bpowmod (int2bint(2),bsub(primo,int2bint(1)),primo);
} while ((ris.num.size() != 1)&&(ris.num[0] != 1));
return primo;
}


la mia dim è di 64 appunto ^^
e come detto sopra, i tempi sono leeeeenti. A volte eccessivi, a volte sopportabili...
Grazie in anticipo :)

MegaAlchimista
02-07-2012, 01:33
Innanzitutto sarebbe utile sapere com'è fatta la classe bigInt.
Da una veloce lettura del codice sto immaginando che per rappresentare un numero a 64 cifre tu utilizzi un vettore di dimensione 64 nel quale ogni elemento è una cifra del numero che vuoi rappresentare?

Se è così immagino che il problema maggiore sia proprio quello di poter riuscire a rappresentare un numero tanto grande, a tal proposito effettuando una veloce ricerca su google ho trovato due interessanti discussioni fatte in questo forum:
1)http://forum.html.it/forum/showthread/t-1339166.html
2)http://forum.html.it/forum/showthread/t-1194636.html

Se non è così allora non ho capito qual'è il tuo problema :D
cià

JErikaM
02-07-2012, 08:30
ciao :)
si io inserisco il numero in un vettore da 64 celle , ogni cifra in ogni cella...a volte il numero si genera in fretta..a volte no...ho visto che funziona, ho attes infatti...e il num si crea, quindi e' solo questione di tempo....ma a volte si e' insopportabile...

il campo bigInt e' composto da int sign e vector<int>num

ora mi guardo i due link! grazie :)

ieri ho provato a fare la generazione di due numeri da 32 dentro il vett, con un for che si ferma a meta', un altro che parte da meta' piu' uno fino alla fine. le prime due volte il num si e' generato in 3 minuti...dopo e' arrivato a 10...non so quindi, sara' un caso xD

JErikaM
05-07-2012, 14:19
Volevo chiedere, è possibile generare più cifre all'interno della stessa cella? cioè in ogni cella mettere invece che 0,1,2,3,4,5,6,7,8,9 anche 10,11...quindi numeri a più cifre?

MegaAlchimista
05-07-2012, 16:17
certo: un intero va fino a 2 miliardi e passa

JErikaM
05-07-2012, 19:56
sono riuscita a ottimizzare i tempi inserendo 3 cifre in ogni cella :) ora i tempi sono molto più ristretti...vanno massimo ai 5 minuti :)

MegaAlchimista
06-07-2012, 02:47
brava.. però è troppo 5 minuti...a parte il fatto che puoi inserire tranquillamente fino a 8 cifre, ti consiglio fortemente di utilizzare le librerie di cui si parla nei link che ti ho postato qualche giorno fa, con quelle sicuramente puoi ridurre i tempi fino ad ordini di grandezza di secondi

Loading