Si premette subito che un computer, in quanto macchina assolutamente
priva di arbitrio (ovvero deterministica), non è in grado di
generare dei numeri casuali nel senso letterale del termine.
Quello che si può fare è realizzare
un algoritmo che generi una sequenza di numeri avente le stesse
proprietà statistiche di una sequenza di numeri casuali.
Agli effetti pratici la sequenza generata ha lo stesso valore di
una sequenza realmente casuale, ma il fatto che si utilizzi un
algoritmo implica che è possibile ricreare la stessa
sequenza fornendo all'algoritmo lo stesso valore iniziale
(chiamato appunto seme).
Pertanto è più corretto parlare di generatori di numeri
pseudo-casuali anziché di numeri casuali veri e propri.
L'algoritmo utilizzato in questo sito è noto in letteratura e
la sua "bontà", nel senso che genera una sequenza
con le stesse proprietà statistiche di una sequenza casuale,
è stata dimostrata, con i test statistici del caso.
Si tratta di un generatore di Lehmer, ovverosia un generatore
congruenziale moltiplicativo.
L'algoritmo, a partire dal seme identificato con X0,
è definito in termini ricorsivi nel seguente modo:
Xk+1 = (aXk+c) mod m, k > 0
I numeri generati appartengono all'intervallo [0, m-1] e
- m è un numero intero
- a e c sono numeri interi maggiori o uguali a 0 e minori di m
Di particolare importanza per la bontà della sequenza è la scelta
dei valori di a, c e m.
Nel caso di questo sito i valori scelti sono stati tratti dalla letteratura e sono:
m=2147483647 (231-1), a=1103515245 e
c=0.
L'implementazione deve gestire i casi di overflow che possono capitare
durante la moltiplicazione aXk. Dato che dopo la
moltiplicazione si esegue una operazione di modulo l'overflow può
essere evitato distribuendo la moltiplicazione su più parti e
eliminando i termini più significativi (ovvero le cifre più a
sinistra). Per fare ciò si può usare l'algoritmo di Schrage
(vedi listato).
Ecco un estratto della classe, in linguaggo C++, che implementa il generatore presente su questo
sito (si noti che la sequenza genera numeri reali tra 0 e 1 (1 escluso) in quanto divide
il valore generato per m):
class CLCG {
public:
long Seed, M, A;
CLCG()
{
Seed = 1;
M = 2147483647; // 2^31-1
A = 1103515245;
}
double GetNextValue()
{
// ALGORITMO DI SCHRAGE
long Q, Z, lo, hi, test;
Q = M / A;
Z = M % A;
hi = Seed / Q;
lo = Seed % Q;
test = A*lo - (long)(Z*hi);
Seed = (test > 0) ? test : test + M;
return (double) Seed / M;
}
};
e qui di seguito un breve programma che usa la classe precedente e con cui si possono
riprodurre le sequenze di numeri generate da questo sito:
void main(void) {
CLCG LCG;
long min, max, n;
cout << "Min? "; cin >> min;
cout << "Max? "; cin >> max;
cout << "Seme? "; cin >> LCG.Seed;
cout << "Quanti numeri? "; cin >> n;
cout << "ATTENZIONE: non si eliminano i duplicati" << endl;
while (n--)
cout << long(min + LCG.GetNextValue() * (max-min) + 0.5) << endl;
}