3 ms·
Does your claim stay for the r() with the period longer than 2 to 100, the shortest in the algorithms he presents?
by acqq 15y ago
Does 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.