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;
perché pensi che generi una distribuzione uniforme? – Alnitak