|
|
|
![]() |
|
Strumenti |
![]() |
#1 |
Senior Member
Iscritto dal: May 2002
Città: somewhere in Europe
Messaggi: 2554
|
generazione di numeri casuali
Credo che il problema della generazione di numeri casuali (pseudo-casuali) sia ben noto a tutti qui.
Riassumendo, in programmazione oggigiorno se si ha la necessita' di generare un numero casuale si usera' una funzione generatrice che non generera' numeri perfettamente casuali bensi' una serie di numeri che avranno una frequenza di ripetizione molto bassa. La mia domanda e': in linguaggi come il C quando si inizializza una variabile dentro ci saranno dei valori "strani", possono essere considerati casuali? Intuitivamente mi rispondo da solo: No, perche' prima probabilmente c'era un programma che scriveva nello stesso spazio di memoria, per cui mettiamo caso che un programma scrivesse tutti 1111 in quella zona di memoria trovero' ancora delgi 1111 Ma se alloco della memoria prima di ogni altro processo, che valori trovero' in RAM? Si potrebbero definire casuali? la vostra ![]() |
![]() |
![]() |
![]() |
#2 | |
Member
Iscritto dal: Jul 2008
Città: Reggio Emilia
Messaggi: 290
|
Quote:
Ma perchè non usare la funzione random()? |
|
![]() |
![]() |
![]() |
#3 | |
Senior Member
Iscritto dal: May 2002
Città: somewhere in Europe
Messaggi: 2554
|
Quote:
![]() la funzione random() non restituisce dei valori casuali ma pseudo-casuali. Il che vuol dire che restituisce delle sequenze di numeri che si ripetono. ad esempio 10 - 2 - 187 (dopo moltissimi numeri ritroverai la stessa sequenza esattamente come all'inizio) |
|
![]() |
![]() |
![]() |
#4 | |
Senior Member
Iscritto dal: Nov 2005
Messaggi: 2773
|
Quote:
|
|
![]() |
![]() |
![]() |
#5 | |
Member
Iscritto dal: Jul 2008
Città: Reggio Emilia
Messaggi: 290
|
Quote:
![]() Probabilmente la sequenza si ripete perchè la funzione random() legge un registro della CPU, forse quello degli indirizzi, non ricordo ![]() Ma perchè ti servono numeri così tanto, passami il termine, casuali? ![]() |
|
![]() |
![]() |
![]() |
#6 | |
Senior Member
Iscritto dal: May 2002
Città: somewhere in Europe
Messaggi: 2554
|
Quote:
I numeri casuali servono in generale in informatica, ad esempio sono usati molto in sicurezza per generare chiavi sicure. |
|
![]() |
![]() |
![]() |
#7 |
Senior Member
Iscritto dal: May 2002
Città: somewhere in Europe
Messaggi: 2554
|
|
![]() |
![]() |
![]() |
#8 | |
Senior Member
Iscritto dal: Nov 2005
Messaggi: 2773
|
Quote:
Ho detto tutti zeri andando a logica, non vedo perché all'accensione la ram dovrebbe contenere dei valori (ma soprattutto perché diversi ad ogni accensione). Ovviamente è una mia ipotesi. |
|
![]() |
![]() |
![]() |
#9 |
Senior Member
Iscritto dal: May 2001
Messaggi: 12814
|
Come già detto quando scrivi:
int a; il sistema riserva una area di memoria (sullo stack) che risulta "libera". Ogni processo ha la sua area per lo stack e per l'heap (l'area di memoria dinamica). Chiaramente quando una locazione di memoria non ti serve più (magari perché chiami una free o termini il processo) il sistema non perde tempo a riscriverci "0". All'avvio del sistema succedono molte cose tra cui caricamento di eseguibili vari in memoria per cui è possibile che tu trova locazioni di memoria "sporche". I generatori pseudo-casuali possono essere di diverso tipo, quelli più usati comunemente dovrebbero essere quelli che sfruttano il meccanismo delle congruenze lineari (sostanzialmente si basano sui resti delle divisioni modulo 2^31, maggiore è il modulo usato maggiore sarà il periodo di ripetizione, tuttavia dipendono anche dai semi e da altri parametri). Notare che la divisione per una potenza di 2 è facilmente ottenibile facendo uno shift di bit a destra: Se ho in binario 100 (4), dividerlo per 2 significa shiftare l'1 di una posizione: 10 (2) Questo li rende abbastanza efficienti da implementare. Cmq mi sembra che Linux disponga di un device virtuale particolare da cui estrarre numeri pseudo-casuali basati sul rumore dei segnali elettro-magnetici. Questo dovrebbe renderlo molto efficacie. Edit: trovato -> http://en.wikipedia.org/wiki//dev/random Ultima modifica di WarDuck : 23-02-2010 alle 21:12. |
![]() |
![]() |
![]() |
#10 |
Senior Member
Iscritto dal: May 2002
Città: somewhere in Europe
Messaggi: 2554
|
grazie WarDuck, so bene come funziona la generazione di numeri casuali classica.
La domanda si concentra di piu' su "cosa c'e' nella memoria all'avvio?" Abbiamo tutti zero o valori spuri? |
![]() |
![]() |
![]() |
#11 | |
Senior Member
Iscritto dal: Oct 2006
Città: Roma
Messaggi: 1383
|
Quote:
per quanto riguarda quelle locali il discorso é piu complesso: anche le pagine di stack sono inizializzate a zero, ma spesso una variabile locale non inizializzata assume valori "strani" perché prima dell'invocazione del tuo main é avvenuta l'invocazione dell'entry point del runtime linkato staticamente al tuo programma, il quale ha usato diverse pagine di stack scrivendoci dati arbitrari. ad ogni modo il sistema che tu ipotizzi non é di certo un sistema crittograficamente sicuro. la caratteristica fondamentale di un buon generatore di numeri pseudocasuali non é quella di generare numeri che si ripetono con frequenze molto basse, ma quella di generare numeri impredicibili da una macchina polinomiale. |
|
![]() |
![]() |
![]() |
#12 | |
Senior Member
Iscritto dal: May 2002
Città: somewhere in Europe
Messaggi: 2554
|
Quote:
la mia idea molto brutalmente sarebbe quella di fare un dump della memoria fisica senza avere un OS installato (se mai fosse possibile, o all'avvio dell'OS) per poter vedere che valori ci sono dentro. |
|
![]() |
![]() |
![]() |
#13 | |
Senior Member
Iscritto dal: Oct 2006
Città: Roma
Messaggi: 1383
|
Quote:
dunque, so per certo che i flip-flop, non appena pigliano corrente, partono a fantasia (ho avuto esperienze pratiche in merito), cioé si trovano in stato non affidabile dettato solo da condizioni esterne/ambientali troppo aleatorie e difficili da prevedere, e quindi la tua idea costituirebbe in effetti un sistema crittograficamente sicuro (anche se un po' curioso). tuttavia la cosa ha ancora delle dipendenze: dipende dall'architettura hardware e dalla specifica implementazione; per esempio in un'architettura hardware potrebbe essere richiesto che tutta la RAM venga azzerata all'accensione e, se anche non fosse richiesto, la specifica implementazione (la realizzazione, i circuiti insomma) potrebbe farlo lo stesso. il motivo per cui prima dicevo che come sistema é un po' curioso é che l'uomo ha a disposizione dei sistemi matematici abbastanza affidabili per generare sequenze pseudocasuali piuttosto che affidarsi allo stato aleatorio di un circuito che subisce i fattori fisici dell'ambiente circostante. |
|
![]() |
![]() |
![]() |
#14 | |
Senior Member
Iscritto dal: May 2002
Città: somewhere in Europe
Messaggi: 2554
|
Quote:
ti sei risposto da solo: abbatanza affidabili VS stato aleatorio Dovessi scegliere sceglierei stato aleatorio ![]() Comunque ieri sera ho trovato un paper di un tizio che dumpava la memoria dopo qualche minuto che il pc era spento e ci trovava ancora i valori che erano stati settati dall'OS...guardero' meglio questa sera. |
|
![]() |
![]() |
![]() |
Strumenti | |
|
|
Tutti gli orari sono GMT +1. Ora sono le: 08:46.