vigna
04-11-2014, 07:30 AM
I don't know if this has been already reported: I couldn't find it in the bug forum.
After describing the Ran generator, NR says:
"If you need a random integer between 1 and n (inclusive), say, then the expression 1+myran.int64() % (n-1) is perfectly OK (though there are faster idioms than the use of %)."
This is true only if n is significantly smaller than 2^w, where w is the output width of the generator (say, n <= 2^{w/2}). In this case the bias is small.
Otherwise, using the modulo leads to heavily biased output. For instance, if w=64, and you need an integer in [0..2^63+2^62), using % will result in the integers in [0..2^62) being twice more likely than the other integers.
After describing the Ran generator, NR says:
"If you need a random integer between 1 and n (inclusive), say, then the expression 1+myran.int64() % (n-1) is perfectly OK (though there are faster idioms than the use of %)."
This is true only if n is significantly smaller than 2^w, where w is the output width of the generator (say, n <= 2^{w/2}). In this case the bias is small.
Otherwise, using the modulo leads to heavily biased output. For instance, if w=64, and you need an integer in [0..2^63+2^62), using % will result in the integers in [0..2^62) being twice more likely than the other integers.