Introduzione: Come fa un computer,che e' la macchina deterministca per eccellenza, a generare numeri a caso?

Cosa succede: Un famoso matematico, von Neumann, disse che chi pensa che un computer possa generare numeri a caso deve essere in uno stato di peccato. In effetti, al tempo di Neumann, c'erano solo due modi per generare numeri a caso: o usare un fenomeno cosi' complesso che e' impossibile prevederne il risultato(ad es. lancio di un dado) oppure con un fenomeno intrinsecamente casuale(ad es. decadimento radioattivo). Il computer invece puo' solo fare le 4 operazioni aritmetiche . Come si possono generare numeri a caso con una macchina cosi' semplice e prevedibile? I primi programmatori trovarono questa semplice ricetta:

  1. Si parte da un numero qualsiasi (chiamato "seed").
  2. Lo si moltiplica per un altro numero P1
  3. Si somma un numero P2 
  4. Si divide il risultato per N prendendo il resto della divisione
Otterrete cosi' il primo numero a "caso". Per ottenere il secondo basta ripetere 1-4 sul numero ottenuto e cosi' per il terzo,etc.
Vediamo un piccolo esemepio con i seguenti valori:

x 0 =79, N = 100, P 1 = 263, and P 2 = 71
x
1 = 79*263 + 71 (mod 100) = 20848 (mod 100) = 48,
x 1 = 48*263 + 71 (mod 100) = 12695 (mod 100) = 95,
x 1 = 95*263 + 71 (mod 100) = 25056 (mod 100) = 56,
x 1 = 56*263 + 71 (mod 100) = 14799 (mod 100) = 99,
I numeri successivi sono: 8, 75, 96, 68, 36, 39, 28, 35, 76, 59, 88, 15, 16, 79, 48. La sequenza quindi si ripete. Questo indica una debolezza del nostro generatore d'esempio: se i numeri casuali sono tra 0 e 99 ciò che si vorrebbe ottenere è che ciascun numero tra 0 e 99 appartenga alla sequenza.
I parametri P 1, P 2 e N determinano le caratteristiche del generatore di numeri casuale e la scelta di x 0 determina la particolare sequenza di numeri casuali che viene generata. Se il generatore viene eseguito con lo stesso seed, genererà sempre la stessa sequenza. In questo senso i numeri generati non sono casuali. Pertanto vengono indicati come numeri pseudo-casuali.

Trasformazione della sequenza originale: il generatore di numeri casuali fornito dalla libreria standard del C generà un numero intero compreso tra 0 e RAND_MAX. Per ottenere altri tipi di intervalli, è necessario trasformare i numeri che vengono generati. Ad esempio se voglio ottenere una sequenza di numeri reali compresi tra 0 e 1 è sufficiente dividere il numero generato per RAND_MAX oppure per ottenere un numero intero compreso tra 0 e n è sufficiente calcolare il resto (tramite l'operatore %) della divisione intera tra il numero generato e n + 1.

Generare i numeri casuali in C:
In C esistono due funzioni (entrambre fornite da stdlib.h) rand()che genera il numero casuale e  srand(int numero) che permette di impostare il valore del seed e quindi di generare sequenze sempre diverse.  Per generare sequenze sempre diverse, occorre scegliere un seed diverso per ogni esecuzione del programma. Una possibile soluzione consiste nell'utilizzare come seed il timer del calcolatore ovvero il numero di secondi trascorsi dalla mezzanotte del 1 gennaio 1970. Questo è reso possibile dalla funzione time(0) presente in time.h

Codice d'esempio: estrai.c (html)