I've been taking a look at the random number generator in Lua 5.4.0-work1. I would like to suggest a different implementation of the algorithm 'project', for two reasons:
- it does not fully eliminate the bias for small numbers that are not a power of two
- more importantly: when used to flip a coin (e.g. random(0,1) == 0) it generates a short sequence of 128 values.
The xorshift128+ RNG produces a sequence whose low-order bits are an LFSR sequence. This is a known problem with most pseudo-random number generators of this type. It would be better to not use the low-order bit in the way 'project' uses them.
The algorithm I use most of the time (in C99). It removes all biases, at the cost of two divisions:
uint64_t project(uint64_t lo, uint64_t hi)
{
assert(lo <= hi);
// handle edge cases first:
switch (hi - lo) {
case 0:
return lo; // one-element range
case UINT64_MAX: // lo == 0 and hi == UINT64_MAX
return xorshift128plus();
}
// number of possible values
uint64_t n = max - min + 1u;
// scale == 2**64 / n, calculated as (2**64 - n) / n + 1u
// 'n * scale' is the largest multiple of 'n' <= 2**64
uint64_t scale = (uint64_t)(-n) / n + 1u;
for (;;) {
uint64_t r = xorshift128plus() / scale;
if (r < n)
return lo + r;
}
}
In the case of 'n' being a power of two the high-order bits will be used ('scale' will be a power of two as well)
Similarly: the 'I2d' function should probably shift a 64-bit random value right by 11 bits in stead of masking the value, this would get rid of the dodgy low order bit.
BTW: the author of the xorshift128+ algorithm now recommends replacing it with a slightly different algorithm, which is ever so slightly faster, and has better statistical properties. It has some downsides as well, the two low-order bits both produce an LFSR sequence, it's probably a wash.
It's here:
Thanks for replacing the random number generator, by the way, definitely an improvement.
Gé
