vendredi 18 septembre 2015

Preventing overflow in sampling of random integers

I found a paper recommending the following recipe to generate random integers with proper uniform distribution in the range [a, b]:

int z, c = RAND_MAX / (b-a+1); // must ensure these operations
c *= b-a+1; // do not overflow!
do
{
    z = rand();
} while( z >= c); // require z uniformly in [0,b-a]
return (z % (b-a+1)) + a;

However can someone explain why we do c *= b-a+1 after c = RAND_MAX / (b-a+1) since this could be simplified to c = RAND_MAX, and how this come to overflow? Furthermore won't this be optimized away by the compiler?




Aucun commentaire:

Enregistrer un commentaire