il seme generatore di numeri casuali
Giorgio M
capitolo che tratta delle funzioni, e più in particolare sono arrivato dove
descrive la funzione rand(). Con la funzione rand(), dice il D&D, si ha
bisogno di dare ogni volta in input, durante l'esecuzione del programma, un
numero a piacere, il seme, che così genererà un tot di numeri casuali
(quanti se ne sono impostati nel sorgente). Poi c'è la funzione srand(),
che ti permette di non dover ogni volta inserire in input il seme per far
generare al computer i numeri casuali, poichè prende il seme direttamente
dall'orologio interno al computer. Quello che non ho capito io è: ma come
cavolo funziona sto seme?? Voglio dire, secondo quale criterio il computer,
mediante un numero casuale immesso in input o preso da egli stesso dal suo
orologio interno, può generare numeri casuali. Qual'è il meccanismo che si
innesca? Oltretutto se io immetto lo stesso numero come seme, il computer
mi genera sempre gli stessi numeri, quindi tanto casuale non direi. Forse
opera delle addizioni, moltiplicazioni, o altro?
Mox
>[SNIP] Con la funzione rand(), dice il D&D, si ha
>bisogno di dare ogni volta in input, durante l'esecuzione del programma, un
>numero a piacere, il seme, che così genererà un tot di numeri casuali
>(quanti se ne sono impostati nel sorgente). Poi c'è la funzione srand(),
>che ti permette di non dover ogni volta inserire in input il seme per far
>generare al computer i numeri casuali, poichè prende il seme direttamente
>dall'orologio interno al computer.
Non credo che il D&D la presenti cosi'.
Rand() genera un numero casuale a partire dall'ultimo numero casuale
generato (o da un valore costante iniziale se non specificato
diversamente, detto seed) secondo il metodo (mi pare) della congruenza
lineare.
Srand() serve per inizializzere il seed a un valore qualsiasi, che
PUO' essere anche l'ora corrente.
Es: srand((unsigned)time(NULL));
>[SNIP] Quello che non ho capito io è: ma come
>cavolo funziona sto seme?? Voglio dire, secondo quale criterio il computer,
>mediante un numero casuale immesso in input o preso da egli stesso dal suo
>orologio interno, può generare numeri casuali. Qual'è il meccanismo che si
>innesca? Oltretutto se io immetto lo stesso numero come seme, il computer
>mi genera sempre gli stessi numeri, quindi tanto casuale non direi. Forse
>opera delle addizioni, moltiplicazioni, o altro?
Allora, non e' una generazione di numeri casuali, ma una generazione
di numeri pseudocasuali, ovvero ogni numero e' calcolato
matematicamente secondo determinati algoritmi, a partire dal
precedente.
<CODE src="Sedgewich">
a[0] = seed;
for (i=1; i <= N; i++)
a[i] = (a[i-1]*b+1 % m
</CODE>
Il tutto sta nel scegliere opportunamente "b" ed "m", nonche' nello
scegliere un buon seme (operazione non cosi' fondamentale).
Questo e' solo uno dei metodi piu' semplici e diciamo meno efficienti:
ne esistono molti, alcuni molto piu' complessi. Cerca su google :)
--
Mox
"Trust the programmer."
"Don't prevent the programmer from doing what needs to be done."
"Keep the language small and simple."
"Provide only one way to do an operation."
Gene Hoglan
> di numeri pseudocasuali, ovvero ogni numero e' calcolato
> matematicamente secondo determinati algoritmi, a partire dal
> precedente.
Ti ringrazio, ora ho capito.
Ed esiste un modo per generarli in modo puramente casuale?
Giovanni
a partire dal pentium III (e affini/concorrenti) viene formito un chip di
generazione di
white noise con possibilita' di 'get' dei valori. Su linux devi ricompilare
il modulo del kernel per
usare la funzionalità. Su M$ non so, mi sembra ci sia un programmino o
qualcosa di simile.
Comincia da
http://www.intel.com/design/security/rng/rng.htm
e da
http://www.cs.berkeley.edu/~daw/rnd/
Ciao
Kronos
> a partire dal pentium III (e affini/concorrenti) viene formito un chip
> di generazione di white noise con possibilita' di 'get' dei valori.
Attenzione, non sulla CPU, ma sul SB dei chipset Intel.
> Su linux devi ricompilare il modulo del kernel per usare la funzionalita`.
Ecco, linux e` un caso interessante. Oltre al RNG fornito dalla libreria
C, esiste un generatore di numeri casuali implementato direttamente nel
kernel ed accessibile tramite il device /dev/random (urandom per numeri
"meno random"). La sequenza e` ottenuta campionando il traffico sulle
periferiche di rete, sui dischi e sull'input dell'utente.
Attenzione pero` a non abusare di questo device. Fornisce numeri
con correlazione bassissima, ma il costo e` che per una sequenza
relativamente breve serve molto input. Di solito il pool viene intaccato
solo da programmi che hanno bisogno di una sequenza affidabile (tipo pgp
al momento della generazione delle chiavi). Se hai bisogno molti numeri
e` meglio utilizzare il RNG della libreria C. Al limite puoi sempre
scriverti il tuo generatore.
A questo proposito, come al solito, vedi Numerical Recipes in C
(www.nr.com), capitolo 7.
ciao
Kronos
--
Home: http://kronoz.cjb.net
#include <stdio.h>
int main(void) {printf("\t\t\b\b\b\b\b\b");
printf("\t\t\b\b\b\b\b\b");return 0;}