Visualizzazione dei risultati da 1 a 7 su 7
  1. #1
    Utente di HTML.it
    Registrato dal
    Jan 2012
    Messaggi
    79

    [C] Minimizzare i tempi creazione numeri primi

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

    codice:
    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

  2. #2
    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
    cià

  3. #3
    Utente di HTML.it
    Registrato dal
    Jan 2012
    Messaggi
    79
    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

  4. #4
    Utente di HTML.it
    Registrato dal
    Jan 2012
    Messaggi
    79
    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?

  5. #5
    certo: un intero va fino a 2 miliardi e passa

  6. #6
    Utente di HTML.it
    Registrato dal
    Jan 2012
    Messaggi
    79
    sono riuscita a ottimizzare i tempi inserendo 3 cifre in ogni cella ora i tempi sono molto più ristretti...vanno massimo ai 5 minuti

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

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi
  •  
Powered by vBulletin® Version 4.2.1
Copyright © 2024 vBulletin Solutions, Inc. All rights reserved.