C/C++ - Numeri primi Multithread?

ho implementato il multithreading utilizzando lo standard posix (per la portabilità e per il fatto che l'ho già usato).

Purtroppo ho notato che con l'implementazione del multithreading:
1) l'algoritmo funziona più lentamente
2) verso la fine mi vengono scritti alcuni numeri primi replicati.

Ho pensato che il rellantamente dell'algoritmo fosse dovuto all'utilizzo dei mutex, ne utilizzo due per due operazioni differenti:
-Mutex_lista : lo uso quando devo fare l'inserimento di un elemento in coda alla lista + stampa annessa
-Mutex_Corrente: lo uso quando devo acquisire l'elemento corrente da calcolare, acquisisco il valore in una variabile locale e poi incremento il valore di 2 e sblocco il mutex, così da non avere interferenze durante l'operazione.

Fondamentalmente nella funzione eseguita dal thread vengono eseguite poche funzioni:
inizializzazione di variabili
inizio del ciclo do while
mutex_corrente per l'acquisizione del valore corrente
ciclo for con controllo se il numero corrente è primo
mutex_lista per l'inserimento del valore primo trovato (se c'è
fine ciclo do while
fine thread

Pensate che in questo caso l'utilizzo dei mutex possa soltanto rendere il multithread inutile, visto che i thread sono rallentati dal dover aspettare lo sblocco mutex?

La perdità di efficienza temporale con il multithread è di circa il 5-10%

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

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.

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:

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

Dovrebbe funzionare.

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.

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.

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

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

almeno così parliamo mostrandoti un pò di codice.