Tag: algorithms

Generatore lineare congruenziale

La matematica è per sua natura abbastanza ordinata, abbastanza ripetitiva ed abbastanza prevedibile. Certo, abbastanza.

In un mondo come questo è quindi non proprio banalissimo avere la generazione di numeri che siano veramente, ma veramente casuali. Ci si accontenta spesso di numeri pseudo-casuali (ovvero numeri generati da un algoritmo che pur essendo deterministico produce una sequenza che ha circa le stesse proprietà statistiche di una sequenza casuale) tipicamente perché il vero caso non serve poi a molto ed è computazionalmente difficile da ottenere.

In altre parole esiste un’equazione “semplice” per ottenere una sequenza di numeri che sembra prodotta dal caso. L’algoritmo LCG (Linear Congruential Generator) è uno dei più vecchi, semplici e conosciuti algoritmi che ci danno l’impressione del caso.

L’algoritmo si basa su un modulo (m), un moltiplicatore (A) ed un incremento (C); uno dei valori della successione, il cui periodo è al più m, è quindi definito da:

Xn+1 = (A Xn + C) mod m

Inutile dire che la semplicità dell’equazione (ed il conseguente largo uso anche in algoritmi numerici) si paga in termini di bontà dei risultati; la scelta dei tre coefficienti diventa fondamentale (e potrebbe essere a sua volta il frutto di un generatore di numeri casuali 🙂 ).

Ed ora facciamo qualche prova:

LCG.png

Cose simpatiche:

  • il penultimo caso è l’algoritmo della Borland C/C++
  • se A ed m sono molto maggiori di C, i valori della successione si schiacciano su C
  • nel primo e secondo caso (ed in generale per ogni combinazione di fattori abbastanza semplice e lineare) la successione è tutt’altro che casuale
  • ovviamente più grandi sono (numericamente) i tre fattori e più l’aspetto casuale della faccenda viene fuori.

… pensateci la prossima volta che vi viene chiesto di dire un numero a caso.

WU