2 ms·
You make many fine points. Paul Hsieh goes into some ways to properly correct for the modulus effect here (as well as debunking commonly suggested ways that do
by nkurz 12y ago
You make many fine points.
Paul Hsieh goes into some ways to properly correct for the modulus effect here (as well as debunking commonly suggested ways that don't work): http://www.azillionmonkeys.com/qed/random.html http://www.azillionmonkeys.com/qed/random.html
Alternatively, especially if you have specifically chosen an LCG because you need the periodicity, you can come up with appropriate constants to generate a perfectly distributed set of integers matching the period of your choosing: http://mathaa.epfl.ch/cours/PMMI2001/interactive/rng4.htm http://mathaa.epfl.ch/cours/PMMI2001/interactive/rng4.htm
This second approach not only solves the modulus issue, but can be very useful for things such as parallelizing the shuffling of an array. Your shuffle won't be perfectly random (as in, some sequences will occur more often than others), but it will be properly distributed in the sense that each index will only be used once.
- sjolsen 12y agoMy preferred method—well, actually, my preferred method is to use std::uniform_int_distribution—but in lieu of that, I prefer to use an adapter that builds values in a target range bitwise from values in a source range. The basic idea is to drop off the top of the input range so it's a power of two wide; this makes the bits of the input values independent (i.e., each bit has equal probability of being 0 or 1). You gather enough bits this way to span at least the target range, then again drop off any values exceeding the range's bound. The drop-off method preserves uniformity because any variable uniformly distributed over a set is also uniformly distributed over any subset of that set. Breaking down and building up the binary representation works because uniformity is preserved by the Cartesian product (i.e., X is uniform in A and Y is uniform in B iff (X,Y) is uniform in A×B, where X and Y are stochastic variables) and the binary representation of an integer is just {0,1}^n for some n. The advantage of this method is that you can adapt any input range to any output range without introducing any nonuniformity, cycles, or other "flaws" in randomness (though it will certainly preserve them, if not amplify them). Another interesting thing to note about this algorithm is that you don't technically have to use binary or even a fixed base; given X in A and Y in B, where A and B are subsets of the natural numbers and |B| ≥ 2, (X,Y) ≅ X * (sup(B)+1) + Y. You can, if I'm not mistaken, use this property to derive the first "more reasonable answer" in the first link you gave from the algorithm above, assuming a smaller target range than input range. And if you look closely at "X * (sup(B)+1) + Y," you'll see a relationship with quotients and remainders and, I think, the LCG itself. This is quite interesting stuff.