Generatore lineare congruenziale

Un esempio di generatore di base può essere dato da

${\displaystyle a=3}$

${\displaystyle c=1}$

${\displaystyle m=5}$

${\displaystyle X_{0}=1}$

Ossia:

${\displaystyle X_{i+1}=3\cdot X_{i}+1{\pmod {5}}}$

La sequenza generata è:

${\displaystyle X_{1}=3\cdot X_{0}+1{\pmod {5}}=4}$

${\displaystyle X_{2}=3\cdot X_{1}+1{\pmod {5}}=3}$

${\displaystyle X_{3}=3\cdot X_{2}+1{\pmod {5}}=0}$

${\displaystyle X_{4}=3\cdot X_{3}+1{\pmod {5}}=1}$

${\displaystyle X_{5}=3\cdot X_{4}+1{\pmod {5}}=4}$

${\displaystyle X_{6}=3\cdot X_{5}+1{\pmod {5}}=3}$

Il periodo è uguale a quattro.

Il generatore congruenziale lineare più efficiente ha m uguale a una potenza di 2, spesso m = 2³² o m = 2⁶⁴ perché questo consente di calcolare l'operazione modulo semplicemente troncando i 32 o i 64 bit meno significativi. La seguente tabella lista i parametri degli LCG di uso comune, inclusa le funzioni rand() di alcuni compilatori.

^{[senza fonte]}

Come mostrato sopra, LCG non usa sempre tutti i bit che produce. L'implementazione Java produce 48 bit ad ogni iterazione ma sono ritornati come risultato solo i 32 bit più significativi. Questo poiché i bit più significativi hanno un periodo più lungo. Gli algoritmi che usano questa soluzione sono migliori.

I generatori congruenziali lineari richiedono una memoria minima (tipicamente 32 o 64 bit) per memorizzare lo stato.

Gli LCG non dovrebbero essere usati in applicazioni dove è critico l'utilizzo dell'alta casualità.

Per esempio, non sono adatti per simulazioni Monte Carlo poiché hanno una correlazione tra di loro. Non devono essere usati in crittografia.

Inoltre questi algoritmi tendono ad avere alcuni difetti. Per esempio, se un LCG è usato per scegliere i punti in uno spazio n-dimensionale, i punti giacciono su iperpiani al massimo m^1/n-dimensionali (teorema di Marsaglia). Questo è dovuto ad una correlazione tra valori successivi della successione.

Un altro problema è che negli LCG i bit meno significativi della sequenza generata hanno un periodo più corto di quello della sequenza se m è posto ad essere una potenza di 2. In generale, la n-esima cifra meno significativa nella base b della sequenza prodotta, dove ${\displaystyle b^{k}=m}$ per qualche intero k, si ripete con un periodo al più ${\displaystyle b^{n}}$ .

Nonostante ciò, gli LGC possono essere una buona scelta in alcuni contesti, come per esempio nei sistemi embedded, dove la memoria disponibile è spesso molto limitata; anche nel caso di un videogioco, prendere un piccolo numero dei bit più significativi potrebbe essere sufficiente. I bit meno significativi di un LCG dove m è una potenza di 2 non dovrebbero mai essere usati.

Se è necessario avere numeri pseudocasuali di qualità e una certa memoria è disponibile (~ 2 kilobytes), allora l'algoritmo Mersenne Twister fornisce un periodo molto maggiore (2^19937-1)

• Numeri pseudo-casuali
• Generatore di Fibonacci ritardato
• Generatore hardware di numeri casuali
• Mersenne Twister
• Funzione periodica

• Generazione di numeri casuali (PDF) ^{[collegamento interrotto]}, su www-tlc.deis.unibo.it.
• Generatore di numeri casuali (Regione Emilia-Romagna), su regione.emilia-romagna.it.

Portale Crittografia

Portale Matematica