4 ms·
"To obtain an integer in [0, n[, one may simply take the remainder modulo n" Isn't that the wrong way? IIRC, most PRNGs behave badly in low-order bits. I alway
by cscheid 15y ago
"To obtain an integer in [0, n[, one may simply take the remainder modulo n"
Isn't that the wrong way? IIRC, most PRNGs behave badly in low-order bits. I always heard that you want to keep the high-order bits around instead via the appropriate integer division.
- acqq 15y agoWith a simple LKG you shouldn't do that. There aren't simple LKG's in the implementations to which that sentence refers.
- tzs 15y agoIt's still bad in general even if the PRNG is perfect. For example, suppose r() is a random number generator that generates random integers in [0, 4294967295]. Suppose I want a random integer in [0, 3000000000]. If I simply take r() % 3000000001, I will get a horrible distribution. A given integer in [0, ~1300000000] will occur about 50% more than a given integer in [~1300000000, 3000000000]. Given a perfect uniform random number generator r() generating integers in [0,M-1], r()%n will only be uniform if n divides M. M%n numbers will be overrepresented, appearing approximately 1+n/M times as often as they should.
- acqq 15y agoDoes your claim stay for the r() with the period longer than 2 to 100, the shortest in the algorithms he presents?
- tzs 15y agoYes. My claim holds even for a true random number generator that has no period. It's a pigeon hole problem. If you are trying to put M pigeons in n pigeon holes, and M is not a multiple of n, you can't put the same number of pigeons in each hole. The right way, given r() generates integers in [0,M-1], and you want an integer in [0,n-1], is to first compare r() to floor(M/n)*(n+1). If r() is greater or equal to that, discard that value of r() and try again. Once you have an r below that limit, you can go ahead and it mod n to get your number in [0,n-1]. (Careful for off by one errors in this...I have not double checked my work!) Alternatively, you can reject r() that is less than M%n: while ( (this_r = r()) < M%n ) ; return this_r % n; PS: note that other methods of reducing a range [0,M-1] to [0,n-1] also have to worry about this. It is not limited to just methods using mod. The only difference if you ignore the pigeon hole problem is that the different range reduction methods will differ in how they distribute their bias in the output range.
- jbaagoe 15y agoYou are quite right, of course. One should only tolerate such quick and dirty solutions if M is much bigger than n - but then, that is often the case.
- deleted 15y ago[deleted]
- acqq 15y agoI've made a test to get numbers 0..99 from C stdlib random which gives 16-bit numbers and has a period of 2 to 32 and that was enough to actually see bias if enough numbers (but much less than a period) are generated. Even for such a small range. I'd say the problem is very real, not just theoretic.
- dchest 15y agoModulo bias. https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Modulo_bias https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#M...