Laboratorio di calcolo numerico e informatica

S

∈ N {0}

z(i + 1) := f (z(i)) f

ossia con funzione di mapping allora il generatore è periodico

∈ N

p z(i) = z(i + p)

di periodo e vale . numeri pseudo

Una certa distinzione deve essere fatta tra

random numeri quasi random

e . I primi (PRN) sono numeri

le cui proprietà statistiche sono il più possible vicine a quelle dei

veri numeri random, cioè quelli ottenuti da processi sici intrin-

secamente random (es. i tempi di attesa tra clicks successivi di

un contatore Geiger). Questi numeri mostrano una correlazione

trascurabile. Al contrario i numeri quasi random (QRN) sono

prodotti per fornire una una distribuzione più regolare nello spa-

zio. Questa proprietà li rende molto utili nel caso di simulazioni

Monte Carlo. In questo caso, per una data sequenza, forniscono

una stima più accurata rispetto ai numeri pseudo-random.

4.0.1 Algoritmi di generazione

Esistono diverse classi di generatori di numeri pseudo-casuali, che

si dierenziano per il tipo di algoritmo usato. Nella quasi totalità 0

essi producono una sequenza di numeri interi uniformemente distribuiti tra e un certo valore

0 1

massimo, oppure di numeri reali tra e (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 valo-

seme seed

re a un parametro numerico, o gruppo di parametri, che viene chiamato ( ). Ogni volta

che si usa lo stesso seme, si otterrà sempre la stessa identica sequenza. Il periodo di un genera-

tore non può quindi superare il numero dei possibili valori del seme: per esempio un generatore

32 bit

il cui seme è immagazzinato in un'unica variabile a potrà avere al massimo un periodo

32 32 −1

2 2

di (solitamente il valore zero non è consentito e quindi i valori possibili sono in eetti ).

Le principali classi di generatori di uso corrente sono

generatori congruenti lineari LCG, linear congruential generators

• ( ): questa è la prima

classe in ordine di tempo ad essere stata utilizzata, e tuttora la più diusa;

generatori di Fibonacci ritardati lagged Fibonacci

• ( ): sono in grado di generare se-

quenze molto lunghe. Tra questi va segnalato l'algoritmo Mersenne Twister, che ha un

19937 −

2 1

periodo di ;

registri di traslazione a retroazione lineare

• ;

registri di traslazione a retroazione generalizzata

• . 23

4.1. TECNICA DI CONGRUENZA LINEARE (LEHMER, 1951)

4.1 Tecnica di congruenza lineare (Lehmer, 1951)

Uno dei metodi più utilizzati per la generazione di numeri casuali è la Tecnica di congruenza

lineare (Linear Congruential Method). La relazione ricorsiva alla base di tale tecnica è

1

z(i + 1) = (a z(i) + b) mod n

dove

• →

a moltiplicatore;

• →

b incremento;

• →

n modulo;

• →

z(i = 0) valore iniziale (seme).

a, b, n, z mod

sono numeri interi non negativi l'operazione rappresenta il resto della divi-

0

sione. lineare ane moltiplicativo

b> 0 b = 0

Se il generatore è detto , se invece è detto .

La tecnica di congruenza lineare presenta le seguenti caratteristiche

• n )

è periodica di periodo (

• −

0, 1/n, 2/n, ..., (n 1)/n

i numeri generati sono discretizzati (solo valori ) perchè la proba-

z(i + 1) 0.5/n, 0.6/n

bilità che assuma valori come è nulla. ( )

Teorema di Knuth z(i + 1) = (a z(i) + b) mod n

Un RNG denito dalla ricorrenza ha

p n

periodo coincidente con il valore massimo se e solo se

• b n

ed sono primi tra loro;

• −

p n a 1 p

se è un divisore primo di , anche deve essere divisibile per ;

• −

4 n a 1 4

se è un divisore di , allora anche deve risultare divisibile per .

−

n 1 n

In questo modo la massima lunghezza di è possibile solo se è un numero primo.

congruente

1 Il numero residuo è basato sul concetto di congruenza lineare: un intero è detto essere

A

lineare ad un intero modulo , quando . La congruenza signica che è uguale

≡ ≡

R b A R mod b A R mod b A

alla somma dell'intero ed un multiplo intero del modulo (o base) .

R m b

A = R + mb

residuo

Il numero è detto (resto) ed è il resto positivo ottenuto dividendo l'intero per la base . Per

R A b

esempio se e , allora i tre possibili residui sono . In termini di congruenza

A = 10 b = 3 7, 4, 1

( ) ( ) ( )

≡ · ≡ · ≡ ·

10 7 mod 3 10 = 7 + 1 3 4 mod 3 10 = 4 + 2 3 1 mod 3 10 = 1 + 3 3

24 CAPITOLO 4. STOCASTICA SPERIMENTALE

4.2 Generatori Tausworthe

I generatori Tausworthe sono un tipo di generatori moltiplicativi ricorsivi che producono numeri

random. Ha la forma seguente

x = (A x + A x + ... + A x ) mod 2

n+1 1 n 2 n−1 k n−k+1

∈ {0, ∀

x , A 1} i 0, 1 L

dove . Generano sequenze periodiche di segmenti di lunghezza denita ,

i i

come 2

01110, L =5

L =5

Per trasformare la sequenza di lunghezza in numeri naturali (decimali) si interpretano

come rappresentazione binaria di un naturale.

4.3 Algoritmo di Mersenne Twister

Nel 1997 ci fu un notevole balzo in avanti nella tecnologia legata agli algoritmi di generazione

deterministica dei numeri. La proposta di un nuovo metodo detto Mersenne twister, ad opera

di Makoto Matsumoto e Takuji Nishimura, risolse molti problemi che vi erano stati no ad

allora con i PRNG precedenti.

Le caratteristiche di questo metodo che gli hanno permesso di diventare uno dei più sfrut-

tati sono diverse. Prima fra tutti c'è la peculiarità di avere un periodo a dir poco colossale, di

19937 −

2 1

: tale periodo molto grande non è una casualità, è stato infatti progettato apposita-

3

mente per ovviare ai problemi dovuti a dei periodi brevi. In secondo luogo il Mersenne twister

623

è in grado di produrre punti equamente distribuiti in spazi no a dimensioni (per valori di

32 bit ) ed inoltre è uno dei generatori più veloci. L'algoritmo originale tuttavia non è conside-

rato adatto per applicazioni crittograche, anche se sono state proposte delle sue varianti che

invece sarebbero in grado di lavorare in ambito crittograco.

Se pensiamo di avere una serie di sequenze di numeri pseudo random di lunghezza ssa

k k

, possiamo supporre di sfruttare tali sequenze per individuare dei punti su uno spazio

dimensionale. Nel caso in cui i numeri generati dal PRNG fossero realmente casuali, i punti

trovati sarebbero distribuiti in maniera uniforme su tutto lo spazio. Questo è uno dei tanti

criteri per valutare la bontà di un generatore pseudo casuale. Altri criteri sono un lungo

periodo e la velocità, fattore essenziale per ottenere risultati statisticamente buoni.

Ecienza

• : buoni RNG devono utilizzare una quantità ridotta di risorse (memoria);

Ripetibilità

• : partendo dallo stesso seme, devono essere in grado di riprodurre la stessa

sequenza di numeri casuali;

Portabilità

• : devono essere indipendenti dal contesto hardware software

2 .

0 1 2 3 4

· · · · ·

01110 = 0 2 + 1 2 + 1 2 + 1 2 + 0 2 = 0 + 2 + 4 + 8 + 0 = 14

3 Questo periodo spiega l'origine del nome: è un numero primo di Mersenne e alcune delle costanti dell'al-

goritmo sono anch'esse numeri primi di Mersenne. In matematica un numero primo di Mersenne è un numero

primo esprimibile come con intero positivo primo.

p −

M = 2 1 p

p 25

4.4. GENERATORE MINIMAL STANDARD

4.4 Generatore Minimal Standard

Park and Miller descrissero un certo numero di implementazioni di linguaggio ad alto livello

chiamato generatore di numeri random Minimal Standard. Queste implementazioni sono

basate sulla formula congurente lineare moltiplicativa

z(i + 1) = (a z(i) + b) mod c

a = 16807 b = 0, c =

dove il moltiplicatore attualmente usato è mentre gli altri due valori sono

32 −

2 1

.

4.5 Altre distribuzioni

4.5.1 Distribuzione esponenziale

Supponiamo di voler costruire una successione di numeri pseudocasuali come osservazioni dalla

distribuzione esponenziale, ovvero con funzione di distribuzione

−λ x

−

F (x) = 1 e

−1

F

Determiniamo : da −λ x

−

u = F (x) = 1 e

si ricava −λ x

−

1 u = e −λ x

−

ln(1 u) = ln(e )

−ln(1 −

x = u)/λ

−1

⇒ −ln(1 −

F (u) = u)/λ

U [0, 1)

Quindi se è una variabile aleatoria uniformemente distribuita in ,

−1 −ln(1 −

X = F (U ) = u)/λ 1/λ

è una variabile aleatoria con distribuzione esponenziale con media . Quindi, data una

[0, 1)

successione di numeri pseudocasuali con distribuzione uniforme in , possiamo ottenere una

successione di numeri pseudocasuali con distribuzione esponenziale.

4.5.2 Algoritmo di Box Muller (gaussiana)

La trasformazione di Box-Muller è un metodo per generare coppie di numeri casuali indipendenti

e distribuiti gaussianamente con media nulla e varianza uno.

y y x x

Consideriamo due variabili casuali e funzioni di due variabili casuali e , queste

1 2 1 2

(0, 1] x

ultime distribuite uniformemente in . Vogliamo determinare due funzioni delle variabili 1

x y y

e che permettano di ottenere variabili e indipendenti tra di loro distribuite in modo

2 1 2

N (0, 1)

gaussiano standard . Si trova che le trasformazioni cercate sono

√

−2 ln x sen(2 π x )

y = √ 2 1

1 −2

y = ln x cos(2 π x )

2 2 1

y y

Allora e sono variabili aleatorie indipendenti con distribuzione normale di deviazione

1 2

standard unitaria.

26 CAPITOLO 4. STOCASTICA SPERIMENTALE

4.6 Metodo Montecarlo

I Metodi Monte Carlo sono un'ampia classe di metodi computazionali basati sul campionamento

casuale per ottenere risultati numerici.

Il metodo è usato per trarre stime attraverso simulazioni. Si basa su un algoritmo che

genera una serie di numeri tra loro incorrelati, che seguono la distribuzione di probabilità che

si suppone abbia il fenomeno da indagare. L'incorrelazione tra i numeri è assicurata da un test

chi quadrato.

L'algoritmo Monte Carlo è un metodo numerico che viene utilizzato per trovare le soluzioni

di problemi matematici, che possono avere molte variabili e che non possono essere risolti

facilmente, per esempio il calcolo integr