Re: Lua 5.4 random number generator

[Gé Weijers <ge@...>]

On Thu, Mar 22, 2018 at 8:47 AM, Roberto Ierusalimschy <roberto@inf.puc-rio.br> wrote:

Many thanks for your analysis.


>    - it does not fully eliminate the bias for small numbers that are not a
>    power of two

Yes. I guess that, if you keep generating one random number per
nanosecond, maybe you can feel this bias after two months. But we will
remove it.

Some tests are really sensitive to small biases, as I have found out... It won't take two months at 10**9 random numbers per second if the tests are any good.

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

We will try to use the higher-bits to generate the number. But two
divisions seem too expensive.

You're currently using one modulo operation in the simple case, which on my desktop processor (older Core i5) takes longer than a division.

The extra overhead in the common case is one division or slightly less. In the worst case the code ends up doing 0 divisions or modulo operations, but 2 draws from the

random generator on average.

The big issue I had is the short sequence you get when using "random(0, 1)" for coin flips. That's beyond a "slight bias."

 

> 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:
>
> http://xoroshiro.di.unimi.it/

We know about this, but it uses a rotate operation, which we have to
emulate with 32-bit numbers (for the C-89 version). I am not sure it
is worth the effort. But we can change that.

Anyway, no (P)RNG will be good for everybody (fast, good statistical
properties, really random, unpredictable, repeatable when needed,
jumpable, etc.). If you need anything more specific, you should provide
your own.

(What do you mean by "wash" in your message?)

I should know better than using colloquialisms like this on a mailing list with an international audience, my apologies...

Definition of "it's a wash" according to Merriam-Webster.com:

—used to say that something is equal and that one side does not have an advantage You won the first game and I won the second, so it's a wash. 

Thanks,

Gé