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 5

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 10:06
Mercoledì, 07/10/2015
Si, usare i mutex per aspettare implica perdita di tempo, per aspettare appunto. Io ti consiglio di associare una lista ad ogni thread, e quando il thread termina, il programma principale provvede a inserire gli elementi della lista del thread terminato nella lista totale. Magari controllando per non avere doppioni. Comunque il fatto che hai doppioni significa che non hai diviso correttamente gli intervalli fra i quali cercare i numeri primi.

PM Quote
Avatar
osharko (Normal User)
Pro


Messaggi: 124
Iscritto: 16/04/2011

Segnala al moderatore
Postato alle 12:05
Mercoledì, 07/10/2015
Testo quotato

Postato originariamente da TheDarkJuster:

Si, usare i mutex per aspettare implica perdita di tempo, per aspettare appunto. Io ti consiglio di associare una lista ad ogni thread, e quando il thread termina, il programma principale provvede a inserire gli elementi della lista del thread terminato nella lista totale. Magari controllando per non avere doppioni. Comunque il fatto che hai doppioni significa che non hai diviso correttamente gli intervalli fra i quali cercare i numeri primi.  



Anche se i doppioni li ottengo solo con il multithread...
P.s. Se faccio come mi suggerisci tu, non posso più avvalermi dell'algoritmo che stavo utilizzando, e cioè di dividere il numero che sto analizzando solo per i numeri primi che lo precedono fino ai numeri primi con valore non maggiore della radice quadrata del numero stesso.

Almenochè non faccio diverse chiamate dal main e ogni volta faccio suddividere il tutto come mi hai consigliato tu.
Es. parto con la lista contenente i primi 100 primi, dopodichè individuo i primi fino a 10000 facendo si che si suddividano i compiti. A questo punto si ritorna al main, controllo se ho raggiunto il valore desiderato, e se non l'ho raggiunto faccio rilavorare i thred...
Dovrei sviluppare un pò meglio la tua idea però, anche perchè così facendo mi sembra che dovrò cambiare alcune cose...
Per caso sapresti aiutarmi a sviluppare l'idea sotto forma di analisi o flowchart o comunque un qualcosa di più preciso prima che possa tradurlo in C?

Grazie per l' aiuto :)

PM Quote
Avatar
TheDarkJuster (Member)
Guru^2


Messaggi: 1620
Iscritto: 27/09/2013

Segnala al moderatore
Postato alle 13:53
Mercoledì, 07/10/2015
Allora.... Io ti descrivo solo l'algoritmo che determina i numeri primi. Questo algoritmo accetta tre parametri: il numero inferiore,  il numero superiore e un puntatore ad una lista di numeri naturali. Hai un numero n che parte dal numero inferiore. Da quel numero trovi il primo numero dispari successivo e maggiore o uguale a 9. A questo punto continui ad incrementare il numero ogni volta di 2. Ogni numero dispari deve essere controllato per vedere se è primo. Quando trovi un numero primo lo metti nella lista puntata dal puntatore in ingresso alla funzione.

Ultima modifica effettuata da TheDarkJuster il 07/10/2015 alle 14:09
PM Quote
Avatar
TheDarkJuster (Member)
Guru^2


Messaggi: 1620
Iscritto: 27/09/2013

Segnala al moderatore
Postato alle 13:59
Mercoledì, 07/10/2015
Per controllare se un numero è primo puoi guardare il resto della divisione intera fra il numero e i numeri 2,3,5,7 e se quei resti sono maggiori di 0 il numero è primo. Quindi hai:
Codice sorgente - presumibilmente C/C++

  1. Bool primo(uint64_t n) {
  2. Return (n%2)&&(n%3)&&(n%5)&&(n%7);}


Dovrebbe funzionare.

PM Quote
Avatar
TheDarkJuster (Member)
Guru^2


Messaggi: 1620
Iscritto: 27/09/2013

Segnala al moderatore
Postato alle 14:08
Mercoledì, 07/10/2015
Questo algoritmo non è il massimo perché ogni numero dispari subisce quel controllo. Se vuoi renderlo ulteriormente più veloce trova un modo probabilistico di sapere se un numero è primo che sia più veloce del controllo descritto sopra e esegui quello. Se il risultato del test probabilistico è positivo fai il controllo più lento ma accurato. Questo dovrebbe essere sufficiente per garantirti maggior velocità. Ti consiglio inoltre di eseguire contemporaneamente un numero di thread non superiore a 4.

PM Quote
Avatar
TheDarkJuster (Member)
Guru^2


Messaggi: 1620
Iscritto: 27/09/2013

Segnala al moderatore
Postato alle 14:14
Mercoledì, 07/10/2015
Più rendi veloci il metodo probabilistico e/o quello accurato più l'algoritmo sarà performante. Il top sarebbe poter trovare il numero primo successivo a quello attuale, ma siccome per il momento non è possibile o lo scopri o ti devi accontentare di ottimizzare il più possibile quei due algoritmi.

PM Quote
Avatar
osharko (Normal User)
Pro


Messaggi: 124
Iscritto: 16/04/2011

Segnala al moderatore
Postato alle 17:48
Mercoledì, 07/10/2015
Testo quotato

Postato originariamente da TheDarkJuster:

Per controllare se un numero è primo puoi guardare il resto della divisione intera fra il numero e i numeri 2,3,5,7 e se quei resti sono maggiori di 0 il numero è primo. Quindi hai:
Codice sorgente - presumibilmente C/C++

  1. Bool primo(uint64_t n) {
  2. Return (n%2)&&(n%3)&&(n%5)&&(n%7);}


Dovrebbe funzionare.  



Ammetto che non capisco bene il tuo codice.. ma purtroppo superato il valore 49, non basterà più a controllare se un numero è primo purtroppo.

il fulcro del mio codice è questo for

Codice sorgente - presumibilmente C/C++

  1. for(primi_now = primi; (primi_now->next) && (curr % primi_now->primo != 0) && (primi_now->primo <= rad); primi_now = primi_now->next);
  2.                         //ogni volta il puntatore primi_now punta alla testa fissa primi
  3.                         //Poi se:
  4.                         //-c'è un elemento successivo
  5.                         //-la divisione tra il nuero corrente e l'elemento che stiamo analizzando è diverso da zero
  6.                         //-il valore per cui stiamo dividendo è non maggiore della radice quadrata del numero corrente
  7.                         //Continuiamo a controllare



almeno così parliamo mostrandoti un pò di codice.

PM Quote
Avatar
lumo (Member)
Expert


Messaggi: 449
Iscritto: 18/04/2010

Segnala al moderatore
Postato alle 18:06
Mercoledì, 07/10/2015
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.

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