Uno dei più semplici, vecchi e diffusamente utilizzati generatori di numeri casuali è quello inventato da D. H. Lehmer nel 1948. Esso è un tipo di generatore congruenziale lineare (LCG).
La formula matematica per generare casualmente numeri tra 0 ed M - 1 è:
Xi = (A × Xi-1 + C) mod M
M è il periodo di questo generatore.
Se vengono generati tutti i numeri tra 0 ed M - 1, si ha il cosiddetto "periodo pieno".
A, C ed M devono essere scelti con cura per produrre lunghe e casuali sequenze di numeri.
Esistono varie condizioni necessarie per generare un periodo pieno. Quelle fondamentali sono:
Esiste poi una serie di altre condizioni che variano a seconda che si scelga un M piuttosto che un altro. Ad esempio: se M = 10q, C non dev'essere divisibile per 2 o per 5, e A (mod 20) = 1.
Se, invece, M = 2q, C (mod 2) = 1 (quindi dev'essere dispari) e A (mod 4) = 1.
Se C = 0, x0 (cioè il numero di partenza) dev'essere diverso da 0.
Per capire meglio, serviamoci di un esempio:
Il ciclo generato dai LCG è limitato dalla macchina che sta eseguendo i calcoli. Perciò, nel caso di un computer con aritmetica a 32 bit (31 bit + il bit del segno), ciò comporta che il massimo di numeri che possono essere generati prima che la sequenza si ripeta è 231 - 1, cioè 2.147.483.647.
Park e Miller stabilirono che i parametri minimi da utilizzare nel generatore congruenziale di Lehmer fossero: A = 75 = 16807, C = 0 ed M = 231 - 1 (un numero primo di Mersenne), perché questa combinazione era stata controllata in dettaglio e le sue caratteristiche erano ben note.
In seguito sono state individuate altre buone combinazioni di parametri, come ad
es.:
| M | A | C | |
| 32 bit | 232 | 69069 | 0 o 1 |
|---|---|---|---|
| 232 | 1664525 | 0 | |
| 231-1 | 16807 | 0 | |
| 231 | 1103515245 | 12345 | |
| 64 bit | 259 | 1313 | 0 |
E' anche possibile provare il generatore congruenziale di Lehmer con parametri personalizzabili.
Ritorna alla pagina principale.
Ritorna alla homepage di Lorenzo Azzalini.