-  [WT] [Home] [Cerca] [Impostazioni]

Nome
Email
Soggetto   (new thread)
Messaggio
File 1
File URL 1
Embed   Help
Password  (per cancellare post e file)
  • Tipi di file supportati: GIF, JPG, PNG
  • Dimensione massima del file: 2000 kB.
  • Le immagini più grandi di 250x250 pixel saranno ridotte.
  • Attualmente ci sono 367 post unici. Visualizza catalogo
  • Blotter aggiornato: 2010-04-28 Mostra/Nascondi Mostra tutto

File 140512821810.jpg - (36 KB , 433x455 , C-logo.jpg )
14965 No. 14965 hide watch expand quickreply [Risposta]
Salve, sto realizzando un programma molto potente in C++, però sono arrivato ad un dilemma, come posso sapere il numero di cifre della mia variabile? Sto utilizzando la libreria gmp e quindi il tipo variabile non è generico ma ho visto che la maggior parte dei comandi comuni sono compatibili. Mi serve un metodo istantaneo, ho già provato a spostare la variabile su stringa e leggerne le cifre ma impiega troppo tempo... (si parla di numeri da 48 milioni di cifre), di dividere per 10 con un loop non se ne parla. Quello che cerco è un metodo istantaneo per saperlo, andrebbe bene anche sapere il peso di questa variabile in bytes. Vi ringrazio in anticipo per l'aiuto.
6 posts omessi. Clicka Risposta per vederli.
>> No. 14973
>>14971
Innanzitutto ti ringrazio tantissimo per l'aiuto, ieri sera mi ero messo d'impegno e con la documentazione sono riuscito a convertire mpz_class in mpz_t per poi ottenere ciò che volevo. Poi ho provato a utilizzare mpz_pow_ui ma i tempi che impiega sono pressochè simili (penso identici) a quando faccio la moltiplicazione così:
mpz_class y;
y=y*y;
Quindi penso che gli algoritmi di moltiplicazione di GMP vengano usati anche in questo caso.
Comunque il mio programma sfrutta il test di Lucas-Lehmer, per non calcolare il risultato della successione che sarebbe elevatissimo (sò già che GMP ha già una funzionalità simile al suo interno ma volevo provare a vedere a che risultati riesco a giungere senza usarla). Praticamente il metodo che uso io consiste nel fare un'elevamento al quadrato e una divisione modulo per n volte, dove n è il numero di Mersenne, quindi col numero che sto testando circa 330.000.000 di volte. Cercando su internet ho trovato un "trucco" per velocizzare la divisione modulo che adesso è pressochè istantanea, il problema rimane la potenza che arriva a dare un risultato di 200.000.000 di cifre in decimale. Quando io dico che impiega molto tempo intendo in realtà 4 secondi, solo che visto che deve essere ripetuto n volte, in totale sono 40 anni. Spero di essermi spiegato bene. (il metodo funziona e calcola molto velocemente numeri con 10 mila cifre)
Ora, visto che l'algoritmo ha raggiunto quello che penso sia il suo apice, volevo cercare di gestirlo al meglio, ovvero il mio pc non usa la massima cpu (17%) quando questo programma è aperto, questo è dovuto anche al fatto che ho 6 core e ne viene utilizzato solo 1 mentre io ho intenzione di utilizzarne più insieme quindi ho bisogno di suddividere la moltiplicazione in dei lavori di equidifficoltà per i miei core (non vi è altra soluzione credo, visto che si tratta di una successione e non posso anticipare i calcoli successivi senza aver svolto i precedenti) e visto che conoscevo l'algoritmo di karatsuba ho pensato di usare quello per suddividere una moltiplicazione in 3 moltiplicazioni più semplici (poi GMP avrebbe provveduto a svolgere queste moltiplicazioni con FFT), non mi aspettavo che questo metodo avrebbe ridotto di un terzo i tempi però mi aspettavo comunque un miglioramento che non ho ottenuto, anzi ho avuto un incremento dei tempi per quanto riguarda il test con numeri "piccoli" (10.000 cifre) mentre per i numeri enormi ho avuto un lieve miglioramento. Sfortunatamente io studio elettronica e d'informatica me ne intendo in maniera discreta...
Ti mando comunque parte del listato sperando che tu riesca a darmi qualche consiglio:
questa parte dovrebbe effettuare un elevamento al quadrato, suddividendo la moltiplicazione in 3 parti ognuna delle quali viene svolta da un core della CPU:
mpz_set(op,y.get_mpz_t());
ccifre=mpz_sizeinbase(op, 4);
l=y>>ccifre;
r=(l<<ccifre);
r=y-r;
som=r+l;
Messaggio troppo lungo. Clicka qui per vedere l'intero messaggio. Espandi Thread
>> No. 14974
>>14973
Quello che dici potrebbe funzionare.

Ho messo qui una implementazione di Lucas-Lhemer che ho buttato giù in una mezz'ora: http://ideone.com/9KydXc (compilare con gcc sorgente.c -lgmp). Usala per comparare lo speed-up della tua tecnica.

Probabilmente puoi ottenere degli speed-up decenti anche senza ricorrere a pachidermi come OpenMP ma usando semplicemente il threading. Tieni aggiornato il filo, per una volta abbiamo qualcosa di interessante di cui discutere.
>> No. 14975
>>14973
> mpz_class y;
> y=y*y;

Nella fretta avevo confuso l'elevamento al quadrato con l'elevamento a potenza di 2. Hai ragione, GMP traduce l'elevamento al quadrato come una moltiplicazione del numero per se stesso, qui sotto il codice di GMP rilevante:


void
mpz_pow_ui (mpz_ptr r, mpz_srcptr b, unsigned long int e)
{
/* We test some small exponents here, mainly to avoid the overhead of
mpz_n_pow_ui for small bases and exponents. */
switch (e)
{
case 0:
Messaggio troppo lungo. Clicka qui per vedere l'intero messaggio. Espandi Thread
>> No. 14976
>>14975
Grazie ancora per il supporto che mi dai, ho compilato il listato che mi hai dato e risulta più lento rispetto a quello che ho portato avanti finora:
scegliendo p=44497,
il tuo programma impiega 13.262 secondi
il mio programma senza OpenMP 3.19 secondi
il mio programma con OpenMP 11.87
Come già detto la mia soluzione con OpenMP per numeri "piccoli" risulta più lenta. C'è anche da considerare il fatto che io per caricare il numero di Mersenne prima lo scrivo su un file testo con un altro programma poi lo leggo ed eseguo il test col programma principale. Il programma che mi hai mandato tu invece lo calcola al momento ed in questo è svantaggiato però non penso sia questo a renderlo più lento ma:
mpz_mod(s, s, m);
operazione che io eseguo in altro modo, quasi istantaneo.
Adesso voglio provare ad usare il threading come mi hai consigliato, ho scelto OpenMP proprio perché non me ne intendo e con una ricerca google è la prima cosa che ho trovato che si avvicinasse a ciò che cercavo. Se riesco ad ottenere significativi miglioramenti (ed in teoria dovrei) voglio fare in modo di eseguire il mio programma su un cluster. Inoltre scommetto che esiste un metodo più efficiente per suddividere una moltiplicazione in più moltiplicazioni meno complesse solo che devo ancora cercare.
>> No. 14977
>>14976
Ho provato ad utilizzare la classe <thread>, i tempi sono gli stessi se non leggermente superiori a quando uso OpenMP, però non ha gli svantaggi di quest'ultima (a volte quando chiudo il programma questo rimane bloccato per una decina di secondi) quindi continuerò ad utilizzarla. Penso che a questo punto bisogna andare a cercare il modo di dividere la moltiplicazione in più operazioni di equiprobabilità in modo efficiente, vedrò di fare qualche ricerca.


File 139222357434.jpg - (8.36KB , 292x173 , cb.jpg )
14853 No. 14853 hide watch expand quickreply [Risposta]
c'è qualche anon che si intende di radio cb?
3 posts e 1 immagine omessi. Clicka Risposta per vederli.
>> No. 14882
>>14881
l'ingegnere progetta, l'operaio costruisce. don't panic
>> No. 14888
https://cdn.mediacru.sh/BM-TB92xZ8_i.png
>> No. 14889
ciao io ho il mio midland alan 28 collegato al mio bmw station wagon nera, (quella interni alquamntara) chiedimi tutto quello che vuoi,
>> No. 14962
Volevo costruire una bella Yagi per ascoltare le radio tunz tunz che arrivano dalla corsica, che piani mi consiglia diochan?
>> No. 14963
>>14962
Ho solo studiato la yagi-uda in teoria, più di nozioni teoriche non ti saprei dire


Cancella post [ ]
Password  
Report post
Motivo  
/r/ Archivio
[0] [1] [2] [3] [4] [5] [6] [7] [8] Prossimo