View Full Version : generazione di numeri casuali
h1jack3r
23-02-2010, 20:17
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 :)
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 :)
Al massimo i valori "strani" che trovi nella variabile sono frutto dell'azione di un programma che ha usato quelle celle della RAM ma che poi ha dichiarato come libera. Quindi quando un programma/processo accede alla RAM in modo ovviamente casuale lascia poi lo "sporco" che ha creato, quindi direi che i valori che potresti ottenere sono casuali. [correggetemi se ho detto fesserie]
Ma perchè non usare la funzione random()?
h1jack3r
23-02-2010, 20:32
Al massimo i valori "strani" che trovi nella variabile sono frutto dell'azione di un programma che ha usato quelle celle della RAM ma che poi ha dichiarato come libera. Quindi quando un programma/processo accede alla RAM in modo ovviamente casuale lascia poi lo "sporco" che ha creato, quindi direi che i valori che potresti ottenere sono casuali. [correggetemi se ho detto fesserie]
Ma perchè non usare la funzione random()?
se rileggi c'e' tutto scritto :) solo in maniera un po' confusionaria...
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)
wingman87
23-02-2010, 20:32
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 :)
Credo che la cosa più logica sarebbe trovare tutti zeri. Comunque immagino dipenda dall'architettura dell'elaboratore.
se rileggi c'e' tutto scritto :) solo in maniera un po' confusionaria...
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)
Uhm si è vero :D
Probabilmente la sequenza si ripete perchè la funzione random() legge un registro della CPU, forse quello degli indirizzi, non ricordo :stordita:
Ma perchè ti servono numeri così tanto, passami il termine, casuali? :O
h1jack3r
23-02-2010, 20:50
Uhm si è vero :D
Probabilmente la sequenza si ripete perchè la funzione random() legge un registro della CPU, forse quello degli indirizzi, non ricordo :stordita:
Ma perchè ti servono numeri così tanto, passami il termine, casuali? :O
no e' proprio una funzione matematica, non legge da nessuna parte.
I numeri casuali servono in generale in informatica, ad esempio sono usati molto in sicurezza per generare chiavi sicure.
h1jack3r
23-02-2010, 20:52
Credo che la cosa più logica sarebbe trovare tutti zeri. Comunque immagino dipenda dall'architettura dell'elaboratore.
parliamo di macchine consumer, le solite architetture x86 x64.
wingman87
23-02-2010, 20:59
parliamo di macchine consumer, le solite architetture x86 x64.
Non saprei però dove cercare, o comunque credo sia una ricerca un po' onerosa, spero ci sia qualcuno che sappia già la risposta.
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.
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
h1jack3r
23-02-2010, 21:17
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?
La domanda si concentra di piu' su "cosa c'e' nella memoria all'avvio?"
Abbiamo tutti zero o valori spuri? parlando di Windows e degli eseguibili nel relativo formato (PE), abbiamo tutti zeri. se in un programma per Windows scritto in C tu non inizializzi una variabile globale, questa risulta nulla.
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.
h1jack3r
23-02-2010, 22:05
parlando di Windows e degli eseguibili nel relativo formato (PE), abbiamo tutti zeri. se in un programma per Windows scritto in C tu non inizializzi una variabile globale, questa risulta nulla.
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.
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.
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. ah, capito, era una domanda di livello molto piu ingegneristico.
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.
h1jack3r
24-02-2010, 08:23
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.
ti sei risposto da solo: abbatanza affidabili VS stato aleatorio
Dovessi scegliere sceglierei stato aleatorio :cool:
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.
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.