nessuno (Normal User)
Guru^2
Messaggi: 6402
Iscritto: 03/01/2010
|
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
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à. |
|
|
Ultimo (Member)
Guru
Messaggi: 877
Iscritto: 22/05/2010
|
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
|
|
|
nessuno (Normal User)
Guru^2
Messaggi: 6402
Iscritto: 03/01/2010
|
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à. |
|
|
osharko (Normal User)
Pro
Messaggi: 124
Iscritto: 16/04/2011
|
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 |
|
|
nessuno (Normal User)
Guru^2
Messaggi: 6402
Iscritto: 03/01/2010
|
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 !
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à. |
|
|
osharko (Normal User)
Pro
Messaggi: 124
Iscritto: 16/04/2011
|
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... |
|
|
nessuno (Normal User)
Guru^2
Messaggi: 6402
Iscritto: 03/01/2010
|
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à. |
|
|
osharko (Normal User)
Pro
Messaggi: 124
Iscritto: 16/04/2011
|
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%
|
|
|
