C.1
C Numeri casuali
C.1 Introduzione
Il prossimo insieme di algoritmi che prenderemo in considerazione è costituito dai metodi utilizzati da un elaboratore per generare numeri casuali. Pur avendo più volte incontrato i numeri casuali in diversi contesti, è bene cominciare a capire cosa siano in realtà.
Capita spesso, durante una conversazione, do confondere il termine casuale (o random) con il termine arbitrario[65]. Avere la necessità di un numero arbitrario significa in realtà che non ha importanza il valore del numero, in quanto un qualsiasi numero è adatto allo scopo. Viceversa, un numero casuale è un concetto matematico ben definito, che identifica un numero estratto da un insieme di valori equiprobabili. Mentre un numero casuale può soddisfare una richiesta di un numeri arbitrario, non è vero il contrario.
Perché abbia senso l’affermazione “insieme di valori equiprobabili”, è necessario limitare i numeri da adoperare ad un dominio finito. Non è possibile avere un numero intero casuale, ma solamente un numero intero casuale appartenente ad un dato intervallo; analogamente, non esiste un numero reale casuale, mentre è possibile parlare di frazioni casuali definite in un certo intervallo ed aventi una precisione stabilita.
Quasi sempre si ha la necessità di gestire non un numero ma una sequenza di numeri casuali (altrimenti ci si potrebbe accontentare di un valore arbitrario). A questo punto ci si appella alla matematico, essendo possibile dimostrare molti risultati riguardanti le proprietà delle sequenze di numeri casuali. Ad esempio, in una sequenza molto lunga di numeri casuali appartenenti ad un dominio ristretto, ci si può aspettare che ogni valore compaia circa allo stesso numero di volte. Le sequenze casuali possono essere sfruttate per modellare molte situazioni naturali, grazie anche alla profonda conoscenza delle loro proprietà. Per usare la terminologia corrente, ci si riferirà ai numeri estratti da sequenze di numeri casuali con il termine di numeri casuali.
Non esiste alcun modo di produrre numeri realmente casuali utilizzando un elaboratore (o un qualsiasi altro dispositivo deterministico). Una volta scritto il programma, tutti i numeri da esso prodotti possono essere in qualche modo dedotti, per cui non è possibile che siano casuali. Il massimo che si può sperare è di scrivere programmi in rado di produrre sequenze di numeri capaci di soddisfare molte delle proprietà dei numeri casuali. Solitamente ci si riferisce a questo genere di
C.2 numeri chiamandoli pseudo-casuali (pseudo-random): questi, pur non essendo realmente casuali, possono essere considerati un’approssimazione dei numeri casuali, così come i numeri in virgola mobile possono essere visti come approssimazioni dei numeri reali.
C.2 Metodo della congruenza lineare
Il metodo più conosciuto per la generazione di numeri casuali, praticamente l’unico utilizzato sin dalla sua introduzione nel 1951 da parte di D.Lehmer, è il cosiddetto metodo della congruenza
lineare[62].
Xn= (c x Xn-1+ao)MOD (Nmax )
In altre parole, per calcolare un nuovo numero casuale, si prende quello precedentemente trovato, lo si moltiplica per una costante c, gli si aggiunge ao e si prende il resto della divisione per un’altra
costante Nmax. Il risultato è sempre un intero compreso tra 0 e Nmax -1. Questo metodo diventa
particolarmente interessante da utilizzare per un elaboratore, vista la semplicità con la quale è solitamente implementata la funzione MOD: se si trascura l’overflow legato all’esecuzione di operazioni aritmetiche, l’hardware stesso della maggior parte degli elaboratori si limita ad eliminare i bit superflui, eseguendo l’operazione MOD relativa a valori di Nmax che superano di uno il più
grande intero rappresentabile in una parola.
C.3 Numeri casuali con distribuzione gaussiana
Fino ad ora si è parlato esclusivamente ( e si continuerà a farlo) di numeri casuali uniformi, per i quali tutti i valori sono equiprobabili. E’ altrettanto comune avere a che fare con numeri casuali che obbediscono ad un altro tipo di distribuzione, per la quale alcuni valori hanno una probabilità maggiore di altri di essere estratti. I numeri pseudo-casuali con distribuzione non uniforme sono solitamente generati effettuando alcune operazioni sui corrispondenti valori uniformemente distribuiti.
Nel nostro caso è stato usato il metodo polare per la generazione di numeri casuali ; questo algoritmo calcola due variabili indipendenti X1 e X2 con distribuzione normale. L’algoritmo è il
seguente [64]:
• P1 [fornisce variabili uniformi]. Genera due variabili indipendenti casuali, U1 e U2,
uniformemente distribuiti tra 0 e 1. Si pone V1 = 2U1-1, V2=2U2-1. (Ora V1 e V2 sono
uniformemente distribuiti tra -1 e +1. Sulla maggior parte dei computer è preferibile avere V1e V2rappresentati in virgola mobile.)
C.3 • P2. [Calcolo S.] Si pone S=V12+ V22
• P3. [E’ SF1 ?] Se SF1, si ritorna al passo P1. (I passi P1 attraverso P3 sono eseguiti 1.27 volte in media, con una deviazione standard di 0.587)
• P4. [Calcolo X1,X2.] Se S=0, si pone X1=X2=0; altrimenti si pone
S S ln 2 V X1 = 1 S S ln 2 V X2 = 2
