Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - Numeri primi Multithread?
Forum - C/C++ - Numeri primi Multithread? - Pagina 4

Pagine: [ 1 2 3 4 5 6 ] Precedente | Prossimo
Avatar
nessuno (Normal User)
Guru^2


Messaggi: 6133
Iscritto: 03/01/2010

Segnala al moderatore
Postato alle 17:53
Mercoledì, 30/09/2015
Testo quotato

Postato originariamente da osharko:
se lo facesse, avremmo trovato un metodo per determinare se un numero è primo, e in matematica non esiste ancora nulla del genere.



Forse ti confondi ...

https://it.wikipedia.org/wiki/Test_di_primalit%C3%A0

Testo quotato


In più il mio li calcola, non l'ho impostato in modo tale che controlli se un numero è primo



Che vuol dire "li calcola" ? Non ha molto senso "calcolare" un numero primo ... questo sì che non ha senso ...


Ricorda che nessuno è obbligato a risponderti e che nessuno è perfetto ...
---
Il grande studioso italiano Bruno de Finetti (uno dei padri fondatori del moderno Calcolo delle probabilità) chiamava il gioco del Lotto Tassa sulla stupidità.
PM Quote
Avatar
Ultimo (Member)
Guru


Messaggi: 869
Iscritto: 22/05/2010

Segnala al moderatore
Postato alle 20:14
Mercoledì, 30/09/2015
non è ancora possibile stabilire con un calcolo matematico quale sarà il prossimo numero primo dopo l'ultimo trovato, quindi l'unico metodo è per tentativi


If ok Then GOTO Avanza else GOTO Inizia

PM Quote
Avatar
nessuno (Normal User)
Guru^2


Messaggi: 6133
Iscritto: 03/01/2010

Segnala al moderatore
Postato alle 20:30
Mercoledì, 30/09/2015
Testo quotato

Postato originariamente da Ultimo:

non è ancora possibile stabilire con un calcolo matematico quale sarà il prossimo numero primo dopo l'ultimo trovato, quindi l'unico metodo è per tentativi  



Appunto ...


Ricorda che nessuno è obbligato a risponderti e che nessuno è perfetto ...
---
Il grande studioso italiano Bruno de Finetti (uno dei padri fondatori del moderno Calcolo delle probabilità) chiamava il gioco del Lotto Tassa sulla stupidità.
PM Quote
Avatar
osharko (Normal User)
Pro


Messaggi: 124
Iscritto: 16/04/2011

Segnala al moderatore
Postato alle 21:01
Mercoledì, 30/09/2015
Testo quotato

Postato originariamente da nessuno:
Che vuol dire "li calcola" ? Non ha molto senso "calcolare" un numero primo ... questo sì che non ha senso ...



Determinare se un numero è primo.

Il Test di primalit... beh è un test probabilistico, non da certezze quindi non direi che l'algoritmo definitivo è stato trovato.

Io semplicemente controllo se ogni numero da 3 (asserisco che 2 è primo e poi parto da 3) 2^64 -1 (esclusi i numeri pari). La "particolarità" sta nel fatto che non confronto tale numero con tutti i precedenti per capire se è primo, ma solo con i numeri primi che lo precedono

PM Quote
Avatar
nessuno (Normal User)
Guru^2


Messaggi: 6133
Iscritto: 03/01/2010

Segnala al moderatore
Postato alle 21:30
Mercoledì, 30/09/2015
Testo quotato

Il Test di primalit... beh è un test probabilistico, non da certezze quindi non direi che l'algoritmo definitivo è stato trovato.



Ma che dici ??

SOLO l'algoritmo di Miller-Rabin è probabilistico ma gli altri no !!

Soprattutto ECPP (basato sulle curve ellittiche) è il più veloce ed usato !

Testo quotato

Io semplicemente controllo se ogni numero da 3 (asserisco che 2 è primo e poi parto da 3) 2^64 -1 (esclusi i numeri pari). La "particolarità" sta nel fatto che non confronto tale numero con tutti i precedenti per capire se è primo, ma solo con i numeri primi che lo precedono



Non ho capito nulla di questa spiegazione. E soprattutto non capisco se TU asserisci o ti basi su qualche principio matematico conosciuto ...

Ultima modifica effettuata da nessuno il 30/09/2015 alle 21:30


Ricorda che nessuno è obbligato a risponderti e che nessuno è perfetto ...
---
Il grande studioso italiano Bruno de Finetti (uno dei padri fondatori del moderno Calcolo delle probabilità) chiamava il gioco del Lotto Tassa sulla stupidità.
PM Quote
Avatar
osharko (Normal User)
Pro


Messaggi: 124
Iscritto: 16/04/2011

Segnala al moderatore
Postato alle 22:30
Mercoledì, 30/09/2015
Testo quotato

Postato originariamente da nessuno:
Non ho capito nulla di questa spiegazione. E soprattutto non capisco se TU asserisci o ti basi su qualche principio matematico conosciuto ...  



-I numeri primi che il mio algoritmo trova vengono memorizzati in una lista.
-Il primo elemento inserito nella lista è 2
-Dopodichè porto il numero corrente a 1 e comincio la scansione ciclica, incremento ogni volta il numero corrente che analizzo di 2 (per saltare i numeri pari)
-Il numero in questione viene diviso per tutti i numeri primi compresi nella lista, finchè questi primi avranno un valore al più uguale a sqrt(corrente)


Ora va meglio? Spero di si...

PM Quote
Avatar
nessuno (Normal User)
Guru^2


Messaggi: 6133
Iscritto: 03/01/2010

Segnala al moderatore
Postato alle 23:12
Mercoledì, 30/09/2015
Ah, ma quindi è il test di primalità basilare, praticamente quello espresso come primo test nella pagina di wikipedia che ti ho indicato.

Quindi, come ti dicevo, adotti un test di primalità, NON calcoli il prossimo numero primo perché NON si può (almeno per ora) fare.

Così come fai hai bisogno della lista dei numeri primi precedenti, ma non è necessario. Il test di primalità lo puoi fare anche testando i valori (ovviamente dispari) fino alla radice di n. In questo modo puoi testare un qualsiasi valore.

Ultima modifica effettuata da nessuno il 30/09/2015 alle 23:19


Ricorda che nessuno è obbligato a risponderti e che nessuno è perfetto ...
---
Il grande studioso italiano Bruno de Finetti (uno dei padri fondatori del moderno Calcolo delle probabilità) chiamava il gioco del Lotto Tassa sulla stupidità.
PM Quote
Avatar
osharko (Normal User)
Pro


Messaggi: 124
Iscritto: 16/04/2011

Segnala al moderatore
Postato alle 15:57
Martedì, 06/10/2015
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%

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