Numeri pseudo-casuali

Da Wikipedia, l'enciclopedia libera.

Sono detti numeri pseudo-casuali (in inglese pseudo-random numbers) i numeri generati da un algoritmo deterministico che produce una sequenza con, approssimativamente, le stesse proprietà statistiche di una sequenza di numeri generata da un processo casuale. Tale algoritmo è detto generatore di numeri pseudo-casuali (PRNG, dall'inglese pseudo-random numbers generator).

Le sequenze di numeri pseudo-casuali vengono solitamente generate da un computer e utilizzate per algoritmi basati su processi casuali, come i metodi di tipo Monte Carlo o le applicazioni di crittografia. Quando invece occorrono sequenze di numeri realmente casuali, si utilizza un generatore hardware di numeri casuali.

Proprietà[modifica | modifica sorgente]

Una sequenza di numeri pseudo-casuali deve soddisfare, al minimo, le seguenti proprietà statistiche:

  • distribuzione degli elementi della sequenza secondo una funzione di distribuzione predefinita f(x): di solito si richiede una distribuzione uniforme su un intervallo specificato (equidistribuzione), cioè f(x) = 1/(x_{max}-x_{min}) nell'intervallo [x_{min},x_{max}] e f(x)= 0 fuori da tale intervallo.
  • indipendenza tra elementi successivi della sequenza: se la funzione di distribuzione per un singolo elemento è f(x), la funzione di distribuzione per le coppie di elementi successivi deve essere f(x,y)= f(x) \cdot f(y).

Ad esempio, la sequenza 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 non si può definire pseudo-casuale, in quanto soddisfa il requisito dell'equidistribuzione (sull'intervallo [1,10]), ma non quello dell'indipendenza: le coppie di elementi successivi non sono uniformemente distribuite sull'insieme di tutte le possibili coppie di numeri da 1 a 10, ma sono tutte della forma (n,n+1) (quindi disegnandole su un grafico cartesiano si dispongono tutte sulla stessa retta). Una sequenza pseudo-casuale potrebbe invece essere ad esempio 3, 2, 10, 9, 6, 8, 1, 5, 4, 7: in questo caso le coppie di elementi successivi appaiono distribuirsi in modo abbastanza uniforme sull'insieme delle coppie di numeri da 1 a 10, anche se la lunghezza della sequenza è troppo breve per poterlo verificare accuratamente.

Alcune applicazioni necessitano di altre proprietà statistiche in aggiunta a queste. In particolare, per le applicazioni di crittografia è essenziale che l'algoritmo non permetta di ricostruire l'intera sequenza avendone osservata una parte: altrimenti un malintenzionato potrebbe riprodurre la chiave crittografica generata a partire dalla sequenza e decifrare le informazioni protette da essa. I generatori che soddisfano questo requisito sono detti crittograficamente sicuri (CSPRNG, cryptographically secure PRNG).

Un'altra proprietà significativa di un generatore di numeri casuali è il suo periodo, ovvero il numero di elementi dopo i quali la sequenza si ripete. In generale più è lungo il periodo e migliore è la qualità del generatore, anche se per la maggior parte delle applicazioni un periodo di 2^{32}-1 (circa 4 miliardi), quale si ottiene per molti generatori di uso comune, è più che adeguato.

Algoritmi di generazione[modifica | modifica sorgente]

Esistono diverse classi di generatori di numeri pseudo-casuali, che si differenziano per il tipo di algoritmo usato. Nella quasi totalità essi producono una sequenza di numeri interi uniformemente distribuiti tra 0 e un certo valore massimo, oppure di numeri reali tra 0 e 1 (questi ultimi si possono sempre ottenere dai primi semplicemente dividendo per il valore massimo).

Prima di essere usato, un generatore deve essere inizializzato assegnando un opportuno valore a un parametro numerico, o gruppo di parametri, che viene chiamato seme (in inglese seed). Ogni volta che si usa lo stesso seme, si otterrà sempre la stessa identica sequenza. Il periodo di un generatore non può quindi superare il numero dei possibili valori del seme: per esempio un generatore il cui seme è immagazzinato in un'unica variabile a 32 bit potrà avere al massimo un periodo di 2^{32} (solitamente il valore zero non è consentito e quindi i valori possibili sono in effetti 2^{32}-1).

Un'attenta analisi matematica è richiesta per assicurare che i numeri generati abbiano le necessarie proprietà statistiche. Robert R. Coveyou dell'Oak Ridge National Laboratory ha intitolato un articolo: "La generazione dei numeri casuali è troppo importante per essere lasciata al caso".

Le principali classi di generatori di uso corrente:

I seguenti sono generatori crittograficamente sicuri:

Distribuzioni non uniformi[modifica | modifica sorgente]

È possibile generare anche sequenze di numeri pseudo-casuali aventi distribuzione non uniforme: se la forma della distribuzione desiderata è data dalla funzione f(x) (di integrale pari a 1) e se \{x_n\} è una sequenza di numeri uniformemente distribuiti nell'intervallo [0, 1], una sequenza avente la distribuzione desiderata si ottiene calcolando y_n = F^{-1}(x_n), dove F è la funzione integrale o funzione cumulativa relativa alla funzione f:

F(x)=\int_{-\infty}^{x}f(y)dy

e F^{-1}(x) è la sua funzione inversa.

Questo metodo va con il nome di metodo di inversione.


Esempio

si vogliono generare numeri pseudo-casuali distribuiti secondo la distribuzione f(x)=e^{-x}. Allora avremo che:

F(x)=\int_{0}^{x}e^{-y}dy=1-e^{-x}.

e

F^{-1}(x)=-\ln(1-x).

Sia ora r la nostra variabile casuale generata uniformemente tra 0 ed 1, poniamo r=F(x), allora

x=-\ln(1-r)

è una variabile pseudo-casuale generata secondo la distribuzione f(x).


Per la distribuzione normale, che non è integrabile in forma chiusa, si usa la trasformazione di Box-Muller.

Numeri pseudo-casuali in C[modifica | modifica sorgente]

Lo standard del linguaggio C (ISO C89) prevede due funzioni dedicate alla generazione di numeri pseudo-casuali:

void srand(unsigned seed);
int rand(void);

La prima funzione inizializza il seme della sequenza, la seconda estrae un numero intero equidistribuito tra 0 e RAND_MAX. Il valore di RAND_MAX dipende dall'implementazione; solitamente è 32767 (2^{15}-1) oppure 2147483647 (2^{31}-1). I prototipi di queste funzioni sono nell'header stdlib.h.

Lo standard non prescrive l'uso di un particolare algoritmo; generalmente viene usato il metodo lineare congruenziale.

Esempio[modifica | modifica sorgente]

La seguente funzione genera una sequenza pseudo-casuale a 16 bit.

uint random;  // global variable which store the random number (16bit)
void randomNext(void) {
  // update random sequence
  // polinomial alghoritm:
  // +> b0 b1 b2 b3 b4 b5 b6 b7 b8 b9 b10 b11 b12 b13 b14 b15
  // |     |  |     |                                     |
  // ------+--+-----+-------------------------------------+
  // carry = b1^b2^b4^b15
  // Pn+1=(Pn<<1)|carry
  uchar randomtmp;  // Just a bit flat to accumulate the ex-OR operations
  if (random==0) random++;  // Note: the seed should be != 0
  randomtmp=0;
  if ((uchar)random&0x02) randomtmp=1;
  if ((uchar)random&0x04) randomtmp^=1;
  if ((uchar)random&0x10) randomtmp^=1;
  if (random&0x8000) randomtmp^=1;
  random<<=1;
  (uchar)random|=randomtmp;
}

Bibliografia[modifica | modifica sorgente]