> Let's move from an over-engineered approach to an under-engineered one.<p>The article says this to deride C++s implementation as being too complicated because it supports ranges such as [-3,17] and then promptly goes on to discuss how a modulo based implementation is very biased if the upper end of the range is above 2^31. It's not really clear why the former use case is unimportant but the latter isn't.<p>It just goes to show that one person's niche use case is another person's main use case. I wish people would just avoid the judgemental term "over engineered" and instead focus on matching appropriate algorithms to appropriate use cases.
In TXR Lisp, the algorithm I put in place basically finds the tightest power-of-two bounding box for the modulus, clisp the pseudo-andom number to that power-of-two range, and then rejects values outside of the modulus.<p>Example: suppose we wanted values in the range 0 to 11. The tightest power of two is 16, so we generate 4 bit pseudo-random numbers in the 0 to 15 range. If we get a value in the 12 to 15 range, we throw it away and choose another one.<p>The clipping to the power-of-two bounding box ensures that we reject at most 50% of the raw values.<p>I don't bother optimizing for small cases. That is, under this 4 bit example, each generated value that is trimmed to 4 bits will be the full output of the PRNG, a 32 bit value. The approach pays off for bignums; the PRNG is called enough times to cover the bits, clipped to the power-of-two box, then subject to the rejection test.
This is well-timed. I don't know much about different random number generators but I do know that we recently had an problem where RNG was a serious performance bottleneck.
I wonder if the "Bitmask with Rejection" method would be more efficient if you sometimes made the mask one bit larger than strictly necessary.<p>As it is, if you want a number in the range 0..8, you take 4 bits of randomness, giving you a number in 0..15. This is great, but 7/16 (43.75%) of the time you have to try again. This not only means more loop iterations, it also means you discard 4 bits of randomness, which may have been costly to generate.<p>If instead you took 5 bits of randomness, you'd be able to accept anything in 0..26 and would only have to reject 27..31, which means only rejecting 5/32 (15.625%) of the time.<p>0..8 is a particularly bad case, though. If you need numbers in the range 0..14, then it's not worth trying to use 5 bits.
It seems crazy to me that there's no way to produce unbiased numbers in an arbitrary range without rejection sampling and a loop. Is there a proof of this?
Personally I'm a fan of the xoshiro[1] generator I have found it to be faster and give more equiprobable outputs.<p>[1]<a href="http://xoshiro.di.unimi.it" rel="nofollow">http://xoshiro.di.unimi.it</a>