[C++] Generatore numeri casuali

[ireon]

Ragazzi non riesco a capire come funziona il generatore di numeri casuali in C++. Considerando queste due funzioni:

void rand_seed()
{
   int seed = static_cast<int>(time(0));
   srand(seed);
}

int rand_int(int a, int b)
{
   return a + rand() % (b - a + 1);
}

Qualcuno potrebbe spiegarmi per bene come funzionano e come fanno a generare numeri casuali? Ad esempio nel seguente codice utilizzando queste due funzioni vengono generati 20 numeri casuali compresi tra 1 e 100... Come funziona il tutto?

int main()
{
   rand_seed();
   vector<int> v(20);
   for (int i = 0; i < v.size(); i++)
   v[i] = rand_int(1, 100);
   print(v);

   return 0;
}

[Ippo343]

http://it.wikipedia.org/wiki/Generat..._congruenziale

[ireon]

http://it.wikipedia.org/wiki/Genera...e_congruenziale

Non ci ho capito niene, qualcuno può spiegarmelo con parole semplici?

[Alex'87]

Originariamente inviato da ireon
Non ci ho capito niene, qualcuno può spiegarmelo con parole semplici?

Hai qualche base di matematica?

[ireon]

Hai qualche base di matematica?

Si

[MItaly]

I generatori di numeri casuali informatici (RNG), nella stragrande maggioranza dei casi*, di fatto non generano numeri davvero casuali, ma forniscono gli elementi di una qualche successione solo apparentemente casuale, come quella riportata nel link che ti è stato postato. Ora, se tu non inizializzassi il generatore di numeri casuali con un seme (seed) all'avvio del programma, l'RNG partirebbe sempre dall'inizio di questa successione, e tu ad ogni esecuzione avresti sempre la stessa sequenza di numeri casuali generata. È per questo motivo che all'avvio del programma si inizializza l'RNG con un seed che dovrebbe essere differente per ogni esecuzione, in maniera tale da partire sempre da un punto differente di questa successione.
Questo è ciò che fa la tua funzione rand_seed: ottiene la data corrente (sotto forma di numero di secondi passati dalla mezzanotte dell'1/1/1970, che è ciò che restituisce time(NULL), e che quindi dovrebbe cambiare ad ogni esecuzione del programma) e, tramite la srand, la usa per inizializzare l'RNG.

In C il generatore di numeri casuali fornisce numeri casuali compresi tra 0 e RAND_MAX (valore molto grande, garantito maggiore o uguale a 32767); tuttavia spesso servono in un altro range, ed è qui che entra in gioco la formuletta usata dalla tua funzione rand_int: rand_int infatti ti consente di ottenere un numero casuale compreso tra a e b in maniera semplice.

Essa prende un numero casuale restituito da rand (e quindi compreso tra 0 e RAND_MAX) e ci applica l'operatore modulo rispetto a (b-a+1); in questa maniera restringe il range del numero tra 0 e b-a (nota però che questo approccio non funziona se b-a>RAND_MAX). Quindi al numero così ottenuto somma a, così ottiene un numero casuale compreso tra a e b.

Da notare che questo metodo naïf di lavorare ha diversi bachi: in primo luogo, se RAND_MAX non è divisibile per (b-a+1) la distribuzione di probabilità, rispetto a quanto restituito da rand, viene falsata, aumentando la probabilità che esca un numero compreso tra a e RAND_MAX%(b-a+1). Inoltre l'algoritmo in questione non tiene conto del fatto che i numeri generati da rand non superano RAND_MAX, per cui se b-a>RAND_MAX tutti i numeri compresi tra (b-a)-RAND_MAX e b non verranno mai generati.

Infine, dato che il valore restituito da time(NULL) ha granularità di un secondo, se il programma viene avviato più volte nello stesso secondo si otterrà la stessa sequenza di valori.

Per i problemi relativi a rand_int si può risolvere in questa maniera:

int rand_int(int a, int b)
{
    return (int)(a + rand() / ((double)RAND_MAX)*(b - a + 1));
}

Per quanto riguarda rand_seed, bisogna ricorrere a funzioni a granularità temporale maggiore, ma lo standard C non fornisce nulla a proposito, per cui bisogna ricorrere a soluzioni platform-specific; su Windows si può usare la GetTickCount(), su sistemi POSIX la gettimeofday.

Naturalmente, tutto questo fermo restando che per qualunque applicazione in cui siano richiesti dei numeri casuali un minimo "seri" (crittografia, generazione password, simulazioni, ...) l'uso di un generatore di numeri casuali migliore è d'obbligo.



* un caso in cui non si tratta di una successione ma di numeri davvero più o meno casuali è /dev/random, che pesca dall'entropia presente nel sistema (movimenti mouse, pressione tasti sulla tastiera, ...) per generare piccole quantità di dati altamente casuali. Dato però che si tratta di pochi valori, questi dati spesso vengono usati come seme sicuro da impiegare in generatori di numeri casuali di qualità crittografica.