Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - Numeri primi Multithread?
Forum - C/C++ - Numeri primi Multithread? - Pagina 6

Pagine: [ 1 2 3 4 5 6 ] Precedente | Prossimo
Avatar
TheDarkJuster (Member)
Guru^2


Messaggi: 1620
Iscritto: 27/09/2013

Segnala al moderatore
Postato alle 18:30
Mercoledì, 07/10/2015
Se è vero che quella prova funziona solo fino al 49 (che non è primo, 7*7=49) allora l'unica è provare tutti i naturali dispari e il 2 fino a radice quadrata di n, se una divisione con uno di quei numeri non ha resto il numero NON è primo.

PM Quote
Avatar
osharko (Normal User)
Pro


Messaggi: 124
Iscritto: 16/04/2011

Segnala al moderatore
Postato alle 18:39
Mercoledì, 07/10/2015
Postato originariamente da TheDarkJuster:

Se è vero che quella prova funziona solo fino al 49 (che non è primo, 7*7=49) allora l'unica è provare tutti i naturali dispari e il 2 fino a radice quadrata di n, se una divisione con uno di quei numeri non ha resto il numero NON è primo.

si ma se salgo molto (tipo a sopra 1milione) il multithreading non varrà di certo quanto ottengo usando il mio algoritmo mi sa..

[quotePostato originariamente da lumo:
Non è facile parallelizzare un crivello comunque. Penso che il massimo che puoi fare sia parallelizzare la parte di crossing out (quando escludi i multipli).
Se il limite superiore è grande, potrebbe convenire parallelizzare questa operazione stessa, ma vedo pochissimi vantaggi.
Si possono in alternativa parallelizzare questi processi sapendo che se ti trovi su n, tutti i numeri nella tabella fino a n^2 sono già definitivamente primi oppure non primi(e quindi puoi già fare il crossing out dei loro multipli).

Se non stai usando un crivello il discorso cambia però. In generale, è difficile perché non puoi suddividere la ricerca arbitrariamente.

Mmmhh... dovrei cambiare la struttura dell'algoritmo come suggeriva prima TheDarkJuster, ma comunque sarebbe un cambio enorme.. probabilmente il mio algoritmo cesserebbe di essere e si trasformerebbe un tutt'altro algoritmo

PM Quote
Avatar
TheDarkJuster (Member)
Guru^2


Messaggi: 1620
Iscritto: 27/09/2013

Segnala al moderatore
Postato alle 18:59
Mercoledì, 07/10/2015
Si, se un algoritmo non è fatto per essere parallelizzato o lo cambi o non parallelizzi il calcolo, semplice.

PM Quote
Avatar
osharko (Normal User)
Pro


Messaggi: 124
Iscritto: 16/04/2011

Segnala al moderatore
Postato alle 19:03
Mercoledì, 07/10/2015
Calcolando i numeri primi fino ad un milione, trovo quasi 80.000 primi. Senza usare i primi, ma tutti i numeri dispari e 2 si dovrebbero analizzare invece 500.000 numeri.
Calcolando i numeri primi fino a 10 milioni, trovo quasi 665.000 primi. Senza usare i primi, ma tutti i numeri dispari e 2 si dovrebbero analizzare invece 5000.000 numeri.
Calcolando i numeri primi fino a 100 milioni, trovo quasi 5.750.000 primi. Senza usare i primi, ma tutti i numeri dispari e 2 si dovrebbero analizzare invece 50000.000 numeri.

Se lavorassi sfruttando circa 30 cores, allora avrebbe senso lavorare senza sfruttare i primi, altrimenti no.
Visto che come si nota, più si va vanti e più i numeri prima diminuiscono e quindi il carico di lavoro diventa proporzionalmente minore.

PM Quote
Avatar
osharko (Normal User)
Pro


Messaggi: 124
Iscritto: 16/04/2011

Segnala al moderatore
Postato alle 19:04
Mercoledì, 07/10/2015
Testo quotato

Postato originariamente da TheDarkJuster:

Si, se un algoritmo non è fatto per essere parallelizzato o lo cambi o non parallelizzi il calcolo, semplice.



Ok, e direi che con questo abbiamo chiuso e io ho sprecato tanti giorni inutilmente xD

Grazie a tutti per il supporto comunque

PM Quote
Avatar
TheDarkJuster (Member)
Guru^2


Messaggi: 1620
Iscritto: 27/09/2013

Segnala al moderatore
Postato alle 19:08
Mercoledì, 07/10/2015
Non hai sprecato giorni. La prossima volta che ti si presenta un problema simile sai se vale la pena di affrontarlo o è meglio non provarci nemmeno.

Hai dovuto rispolverare pthread e i mutex. Chiamalo tempo sprecato.....

PM Quote
Avatar
TheKaneB (Member)
Guru^2


Messaggi: 1792
Iscritto: 26/06/2009

Segnala al moderatore
Postato alle 15:46
Lunedì, 12/10/2015
Un'implementazione comoda multipiattaforma può essere OpenMP.

Invece di gestire i thread e la sincronizzazione a mano, bisogna solo specificare i kernel di esecuzione tramite direttive #pragma.
In questo modo ragioni più sull'algoritmo e meno sui dettagli tecnici, ottenendo comunque prestazioni elevate se l'algoritmo si presta.

PM Quote
Pagine: [ 1 2 3 4 5 6 ] Precedente | Prossimo