lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

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:
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.