Algoritmo ziggurat
L'algoritmo ziggurat è più veloce rispetto ad altri metodi di generazione di numeri casuali normalmente utilizzati, come ad esempio il metodo polare di Marsaglia e la trasformazione di Box-Muller. Tuttavia, poiché questo algoritmo è anche più complesso da implementare, solitamente è utilizzato solo a fronte di una grande richiesta di numeri pseudo-casuali. Il termine ziggurat è stato utilizzato per la prima volta in un articolo di George Marsaglia e Wai Wan Tsang nel 2000. Lo chiamarono così per via del modo in cui distribuisce la probabilità: la distribuzione ricorda la forma di una ziggurat[2] a causa dei segmenti rettangolari impilati in ordine decrescente da cui è formata. Teoria del funzionamentoL'algoritmo ziggurat è basato sulla tecnica del rejection sampling: genera casualmente un punto in una distribuzione più grande di quella desiderata e controlla quindi se il punto generato è valido o meno. Dato un punto casuale al di sotto di una curva di densità di probabilità, la sua coordinata x è un numero casuale con la distribuzione desiderata. La distribuzione scelta dall'algoritmo ziggurat è composta da n regioni di uguale area. Data una funzione di densità di probabilità decrescente monotona y = f (x), definita per tutti i valori x ≥ 0, la base della ziggurat è definita come tutti i punti interni alla distribuzione e sottostanti la retta y1 = f (x1). Questa consiste in una regione rettangolare individuata dai punti (0,0) a (x1,y1), più la coda (tipicamente infinita) della distribuzione, dove x > x1 (e y < y1). Questo livello è detto strato 0 ed ha area pari ad A. Sopra di esso, viene costruito un altro strato rettangolare di larghezza x1 e altezza A / x1, così da mantenere anche per esso un'area pari ad A. La parte superiore di questo livello si trova a y2 = y1 + A / x1 e interseca la funzione di densità di probabilità in un punto (x2, y2), dove y 2 = f (x2). Questo strato include ogni punto della funzione di densità di probabilità compreso tra y1 e y2, ma, a differenza del livello base, include anche punti come (x1, y2) che non si trovano nella distribuzione desiderata. Ulteriori strati vengono poi impilati mantenendo costante l'area. Per utilizzare una tabella precalcolata di dimensione n (256 solitamente), viene scelta x1 tale che xn = 0, il che significa che il livello superiore, il livello n - 1, raggiunge esattamente il picco di distribuzione a (0, f (0)). Generalizzando, lo strato i-esimo si estende verticalmente da yi a yi+1 e può essere diviso orizzontalmente in due regioni: la porzione (generalmente più grande) da 0 a xi+1 che è interamente contenuta nella distribuzione desiderata, e la porzione (generalmente più piccola) da xi+1 a xi, che è solo parzialmente contenuta nella distribuzione. Ignorando per un momento il problema del livello 0, e date le variabili casuali uniformi U0 e U1 ∈ [0,1], l'algoritmo ziggurat opera in questi passi:
Il passaggio 1 equivale alla scelta di una coordinata y. Il passaggio 3 verifica se la coordinata x è all'interno della funzione di densità desiderata. In caso contrario, il passo 4 sceglie una coordinata y e il passo 5 esegue il test di accettazione. Si noti che per il livello superiore n - 1 questo test fallisce sempre, perché x n = 0. OttimizzazioniL'algoritmo può essere eseguito in modo efficiente utilizzando tabelle precalcolate per xi e yi = f (xi), ma si possono apportare alcuni miglioramenti per renderlo ancora più veloce:
Note
Altri progetti
Collegamenti esterniInformation related to Algoritmo ziggurat |