La metà delle applicazioni del calcolo scientifico ad alte prestazioni (basate cioè su computer con architettura avanzata o su sistemi di calcolo parallelo) utilizza un approccio basato su simulazioni di natura statistico-probabilistica a cui generalmente ci si riferisce con il nome di  metodi Monte Carlo. Un problema strettamente collegato all’uso di metodi Monte Carlo è il problema della generazione di numeri casuali.Numeri casuali sono utilizzati per costruire simulazioni di fenomeni fisico-ingegneristici (reattori nucleari, gasdinamica, traffico stradale, …), di problemi decisionali e finanziari (prezzo di un’opzione, previsione Dow-Jones), informatica (crittografia, progettazione VLSI, rendering) o come semplice fonte di divertimento (gioco d’azzardo, videogiochi).

Il forte legame che esiste tra il gioco e le simulazioni statistiche è sottolineato dalla scelta del termine Monte Carlo in riferimento ai famosi Casino di Monaco. La roulette infatti è un esempio di generatore di numeri casuali tra 0 e 36.

Storicamente, l’idea di utilizzare in modo sistematico simulazioni di tipo statistico per risolvere un problema di natura fisica viene attribuita a John Von Neumann e Stanislaw Ulam nell’ambito del progetto americano per la costruzione della bomba atomica (Manhattan project) durante la seconda guerra mondiale tra il 1943 ed il 1945 a Los Alamos, New Mexico. Precedentemente, Enrico Fermi negli anni ’30, per i suoi studi di fisica nucleare, aveva utilizzato metodi tipo Monte Carlo per la simulazione di eventi probabilistici che riguardavano la diffusione casuale di neutroni.

 

In figura il calcolo di π tramite un semplice metodo Monte Carlo.Una volta estratte a sorte N coppie di numeri casuali nel quadrato di lato2, basta calcolare il numero Nc di punti interni alla circonferenza di raggio 1 inscritta nel quadrato. Avremo allora che π potrà essere stimato dal rapporto 4Nc/N.

 

 

Ma cos’è un numero casuale?  Un esempio che tutti ben conosciamo consiste nel lancio di un dado. L’imprevedibilità del numero ottenuto come punteggio, compreso tra 1 e 6, conferisce allo stesso una forma di casualità.

L’idea stessa di utilizzare un calcolatore, quindi un oggetto puramente deterministico (e di conseguenza prevedibile), per generare un numero casuale (quindi imprevedibile) sembra costituire una sfida impossibile.

In effetti, nessun calcolatore è in grado di generare numeri puramente casuali, ma solo  numeri pseudo-casuali  ossia numeri generati da algoritmi matematici in grado di superare una serie di test statistici che conferiscono a questi numeri una apparente casualità. Questi test statistici, ad esempio, verificano che i numeri risultino uniformemente distribuiti e che non siano tra loro correlati. Se lanciamo un dado un certo numero di volte ognuna delle facce da 1 a 6 si presenterà circa 1/6 delle volte originando così una successione uniforme di numeri casuali compresi tra 1 e 6. La sequenza di numeri 1, 2, 3, 4, 5, 6, è uniformemente distribuita nell’intervallo [1, 6], ma è evidente che non ha nessun carattere di casualità dato che i numeri sono strettamente correlati. Le coppie di elementi successivi non sono uniformemente distribuite sull’insieme di tutte le possibili coppie di numeri da 1 a 6, ma sono tutte della forma  (n,n+1), quindi disegnandole su un grafico cartesiano si dispongono tutte sulla retta di equazione y=x+1.

 

 

Rappresentazione delle coppie di punti  (x_n , x_n+1)  nel piano per  un generatore contenente correlazioni LCG con m=31, a=13, c=0 (a sinistra) ed un generatore senza evidenti correlazioni LCG con  m=2³¹-1, a=75, c=0  (a destra).

 

 

Uno dei metodi matematici più noti per generare numeri casuali distribuiti uniformemente è rappresentato dai  generatori lineari congruenziali  o più brevemente LCG. Tali generatori vennero presentati per la prima volta da D.H. Lemer negli anni ’40. Il metodo LCG, come tutti i generatori di numeri casuali, ha bisogno di un seme per inizializzare la sequenza di numeri secondo la regola

x_n+1 = (a x_n + c) mod m,  n≥0,

dove  a,  c  ed  m  sono opportuni numeri interi costanti. La notazione “mod  m”, ossia modulo m, significa che  ax_n+c viene diviso per  m  e  x_n+1  posto uguale al resto intero della divisione. Quindi  x_n+1  assume valori interi tra  0, 1, 2,…., m-1.

Il problema della scelta dei migliori valori per  a,  c  ed  m  è quindi il punto cruciale del metodo. Un aspetto importante è la lunghezza del periodo della successione da cui segue che  m  dovrà essere molto grande. Inoltre per un dato  m  i valori di  a  e  c  dovranno essere tali che la successione abbia periodo massimo. Una delle scelte più popolari è m=2³¹-1, a=75, c=0. Questo garantisce un periodo di oltre due miliardi di numeri casuali. Il fatto che  m  sia un numero primo molto particolare (un numero primo di Mersenne, ossia esprimibile come  2ⁿ-1  con  n  intero positivo primo),  è fondamentale per ottenere il massimo periodo. Il metodo appena descritto non rappresenta un generatore di alto livello dato che non soddisfa diversi test statistici, ma nella sua semplicità evidenzia un’ aspetto importante nella generazione di numeri pseudo-casuali, ossia la necessità di avere a disposizione  moltissimi numeri casuali ed in modo rapido.

Successivamente, sono stati proposti algoritmi matematici con proprietà statistiche migliori. Tra questi i generatori cosiddetti di Fibonacci ritardati, o semplicemente LFG, per la similarità con la sequenza di Fibonacci  x_n+1=x_n+x _n-1, ideati  verso la fine degli anni ’50 da G.J. Mitchell e D.P. Moore,  che arrivavano a produrre oltre 38 milioni di miliardi di miliardi di numeri pseudo-casuali!

Nonostante questo, anche i generatori LFG risultano insoddisfacenti in alcune applicazioni e il loro comportamento dipende molto dall’inizializzazione del metodo. Lo stato dell’arte oggi è rappresentato dal generatore cosiddetto di Mersenne Twister, o MT in breve, una variante dei metodi LFG presentata nel 1997 da M. Matsumoto and T. Nishimura che consente di ottenere successioni di numeri pseudo-casuali incredibilmente lunghe  e in grado di superare alcuni tra i più severi test statistici. Attualmente l’algoritmo MT comunemente implementato in molti linguaggi di programmazione garantisce un periodo colossale, pari al numero di Mersenne  219937-1,  da cui il nome del metodo. Come termine di confronto basti pensare che una stima del numero di atomi che compongono il nostro universo è  10⁸⁰!

 

Lorenzo Pareschi

Dipartimento di Matematica e CMCS

Università di Ferrara