2013-02-04 14 views
6

Perché questo codice genera numeri distribuiti uniformemente? Ho delle difficoltà nel comprenderlo. Qualcuno potrebbe spiegare? Grazie.Generazione di numeri casuali uniformemente distribuiti

int RandomUniform(int n) { 
    int top = ((((RAND_MAX - n) + 1)/n) * n - 1) + n; 
    int r; 
    do { 
    r = rand(); 
    } while (r > top); 
    return (r % n); 
} 

aggiornamento: capisco perché rand()% n non ti dà una sequenza uniformemente distribuita. La mia domanda è perché il

top = ((((RAND_MAX - n) + 1)/n) * n - 1) + n; 

Qual è la preoccupazione qui? Penso che un semplice top = RAND_MAX/n * n possa fare.

+3

perché pensi che generi una distribuzione uniforme? – Alnitak

risposta

10

La funzione presuppone che rand() sia distribuito uniformemente; la validità o meno di un'ipotesi valida dipende dall'implementazione di rand().

Data un'uniforme rand(), è possibile ottenere un numero casuale nell'intervallo [0,n) calcolando rand()%n. Tuttavia, in generale, questo non sarà abbastanza uniforme. Per esempio, supponiamo n è 3 e RAND_MAX è 7:

rand()  0 1 2 3 4 5 6 7 
rand() % n 0 1 2 0 1 2 0 1 

possiamo vedere che 0 e 1 venire con una probabilità di 3/8, mentre il 2 viene solo con una probabilità di 2/8: il la distribuzione non è uniforme.

Il codice ignora qualsiasi valore di rand() pari o superiore al multiplo più grande di n che può generare. Ora ogni valore ha la stessa probabilità:

rand()  0 1 2 3 4 5 6 7 
rand() % n 0 1 2 0 1 2 X X 

Quindi 0,1 e 2 tutti venire con una probabilità di 1/3, fino a quando non siamo così sfortunati che il ciclo non termina.

Per quanto riguarda l'aggiornamento:

Penso che un semplice top = RAND_MAX/n * n farebbe.

Se RAND_MAX fossero un limite esclusivo (uno in più del massimo effettivo), allora sarebbe corretto.Poiché è un limite inclusivo, dobbiamo aggiungerne uno per ottenere il limite esclusivo; e poiché il seguente logica confronta con > contro un limite compreso, quindi sottrarre uno nuovo dopo il calcolo:

int top = ((RAND_MAX + 1)/n) * n - 1; 

Tuttavia, se RAND_MAX erano uguali a INT_MAX, allora il calcolo sarebbe traboccare; al fine di evitare che, sottrarre n all'inizio del calcolo, e aggiungerlo di nuovo alla fine:

int top = (((RAND_MAX - n) + 1)/n) * n - 1 + n; 
+0

Grazie per la spiegazione – JASON

7

Il problema di fondo è questo: si supponga di disporre di un generatore di numeri casuali my_rand() che produca valori compresi tra 0 e 6 inclusi e di voler generare valori compresi tra 0 e 5 inclusi; se si esegue il generatore e si restituisce my_rand() % 6, non si otterrà una distribuzione uniforme. Quando my_rand() restituisce 0, ottieni 0; quando restituisce 1, ottieni 1, ecc. fino a my_rand() restituisce 6; in tal caso, my_rand() % 6 è 0. Quindi, nel complesso, my_rand() % 6 restituirà 0 due volte più spesso di qualsiasi altro valore. Il modo per risolvere questo problema consiste nel non utilizzare valori superiori a 5, ovvero, anziché my_rand() % 5, si scrivono i valori di ciclo e scarto da my_rand() troppo grandi. Questo è essenzialmente ciò che sta facendo il codice nella domanda. Non l'ho tracciato, ma la solita implementazione è calcolare il multiplo più grande di n che è minore o uguale a RAND_MAX, e ogni volta che rand() restituisce un valore maggiore di quello multiplo, torna indietro e ottieni un nuovo valore.

+0

buona spiegazione, ma richiede comunque che l'RNG di input abbia effettivamente una distribuzione uniforme. – Alnitak

+0

@Alnitak - true. –

+0

inoltre, se 'RAND_MAX' è abbastanza grande (che di solito è) e' n' è abbastanza piccolo allora la differenza che il codice sopra rende è trascurabile. – Alnitak

2

non ho tracciare attraverso il codice che calcola in alto, ma RAND_MAX è il valore più grande che rand() può tornare ; (RAND_MAX + 1)/n * n sarebbe un soffitto migliore, ma se RAND_MAX è, ad esempio, INT_MAX, il risultato sarebbe imprevedibile. Quindi forse tutto quel codice sta cercando di evitare l'overflow.

+0

Grazie. Penso di averlo capito. Esatto, n dovrebbe dividere RAND_MAX + 1. e il codice RAND_MAX + 1 - n quindi fare/n * n, che evita l'overflow. Grazie. – JASON

+0

Per alcuni valori di 'n', si otterrebbe un valore inferiore, che, a sua volta, avrebbe sprecato più numeri casuali del necessario. Ad esempio, se 'RAND_MAX' è dispari (che di solito è), e' n' è '(RAND_MAX + 1)/2', quindi in media il codice chiamerebbe' rand() 'due volte per ogni numero casuale che generato. –

+0

Considera quale opzione '(RAND_MAX/n) * n' farebbe per' n = RAND_MAX-1'. –

Problemi correlati