
12

I've been taking a look at the random number generator in Lua 5.4.0work1. 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 loworder bits are an LFSR sequence. This is a known problem with most pseudorandom number generators of this type. It would be better to not use the loworder 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; // oneelement 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 highorder bits will be used ('scale' will be a power of two as well)
Similarly: the 'I2d' function should probably shift a 64bit 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 loworder 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é


On Mar 21, 2018, at 8:57 PM, Gé Weijers <[hidden email]> wrote:
I've been taking a look at the random number generator in Lua 5.4.0work1.
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) =3D=3D 0)=
it
generates a short sequence of 128 values.
The xorshift128+ RNG produces a sequence whose loworder bits are an LFSR
sequence. This is a known problem with most pseudorandom number generators
of this type. It would be better to not use the loworder 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 <=3D hi);
// handle edge cases first:
switch (hi  lo) {
case 0:
return lo; // oneelement range
case UINT64_MAX: // lo =3D=3D 0 and hi =3D=3D UINT64_MAX
return xorshift128plus();
}
// number of possible values
uint64_t n =3D max  min + 1u;
// scale =3D=3D 2**64 / n, calculated as (2**64  n) / n + 1u
// 'n * scale' is the largest multiple of 'n' <=3D 2**64
uint64_t scale =3D (uint64_t)(n) / n + 1u;
for (;;) {
uint64_t r =3D xorshift128plus() / scale;
if (r < n)
return lo + r;
}
}
In the case of 'n' being a power of two the highorder bits will be used
('scale' will be a power of two as well)
Similarly: the 'I2d' function should probably shift a 64bit 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
loworder bits both produce an LFSR sequence, it's probably a wash.
It's here:
http://xoroshiro.di.unimi.it/
I had post the problem earlier: http://luausers.org/lists/lual/201803/msg00332.html
Below version avoided 64bits divisions, at the cost of possibly more generator calls. My timings suggested this is simpler and faster, even with small n
// return unbiased random number ran, 0 <= ran <= n // it tried ran = math.random(2 ^ (bits of n)) until ran <= n // since the range is power of 2, it avoided the expensive 64bits divisions
static lua_Unsigned project(lua_Unsigned ran, lua_Unsigned n, RanState *state) { int bits = __builtin_clzll(n); while ((ran >>= bits) > n) ran = I2UInt( xorshift128plus(state>s) ); return ran; }


seeding the random generator can possibly be simpler (without warmup)
http://xoroshiro.di.unimi.it/, section "Why just sizes 128 and 1024":
For 64 bits, we suggest to use a SplitMix64 generator, but 64 bits of state are not enough for any serious purpose. Nonetheless, SplitMix64 is very useful to initialize the state of other generators starting from a 64bit seed, as research has shown that initialization must be performed with a generator radically different in nature from the one initialized to avoid correlation on similar seeds.

I tried a simpler approach, using Knuth MMIX LCG:
#define LCG(x) (6364136223846793005ULL * (x) + 1442695040888963407ULL)
static void setseed (I *state, lua_Integer n) { state[0] = Int2I(n); // guaranteed not stuck in zero state, state[1] = LCG( Int2I(n)); // and state[0], state[1] very different }


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.
> The xorshift128+ RNG produces a sequence whose loworder bits are an LFSR
> sequence. This is a known problem with most pseudorandom number generators
> of this type. It would be better to not use the loworder bit in the way
> 'project' uses them.
We will try to use the higherbits to generate the number. But two
divisions seem too expensive.
> 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
> loworder 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 32bit numbers (for the C89 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?)
 Roberto


>  more importantly: when used to flip a coin (e.g. random(0,1) == 0) it
> generates a short sequence of 128 values.
By "a short sequence of 128 values" you mean it repeats itself after
128 values?
I generated a sequence of 1000 flips, then another sequence of 128 flips,
and searched for the second inside the first. The maximum match I found
was a subsequence of 13 values.
 Roberto


In reply to this post by Roberto Ierusalimschy


> You're currently using one modulo operation in the simple case, which on my
> desktop processor (older Core i5) takes longer than a division.
I guess most processors (including i5) use the same instruction to
compute a modulo and a division, so they have exactly the same cost.
> 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.
I removed that modulo; it is really more expensive than the general case.
(With it, I removed too its corresponding bias.)
> 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."
Sure it is. But I could not find this sequence (see my other message).
 Roberto


In reply to this post by Roberto Ierusalimschy


In reply to this post by Roberto Ierusalimschy


> Sorry about getting confused about the sequence. Regular linear
> congruential generators produce an evenoddevenodd pattern, so a 128 bit
> sequence sounded reasonable. xorshift128 and its variants are not nearly
> that bad, but there still a relatively simple linear relationship there. If
> you're using it for running a game it probably does not matter, if you're
> running a casino it definitely does.
The '+' in the xorshift128+ aims to remove the linearity of the
algorithm, but it does not affect the lowest bit (it has no carry,
so the '+' performs an xor). But I must confess I have no idea why
linearity is bad.
Our goal are things like games. If you are running a real cassino, you
probably should bring your own PRNG.
 Roberto


On Mar 23, 2018, at 9:11 AM, Roberto Ierusalimschy < [hidden email]> wrote:
> The '+' in the xorshift128+ aims to remove the linearity of the
> algorithm, but it does not affect the lowest bit (it has no carry,
> so the '+' performs an xor). But I must confess I have no idea why
> linearity is bad.
>
What is linearity ?
Does linearity affect randomness (make it predictable) ?


Period 2**128  1: Is it due to all zero state will never happen ?
You mean just two math.random(0) (128 bits) can predict the next one ?
BUT, why Vigna say never use last 2 bits to build double ? I am confused.
The linear dependencies causing the failure of the binaryrank test can be reduced by applying a nonlinear operation on the output: for example, multiplying by a constant, or adding as 64bit integers (thus, in the ring Z/2^{64}Z) two pieces of the state space. This is what happens in the generators described here. With more operations it could be possible to completely eliminate the linear artifacts, but I consider this a waste of time: as we've seen, some of the most used generators around have linear dependencies in every bit, and this is not considered a problem. Note also that when generating floating point values you never use the two lowest bits.


On Fri, Mar 23, 2018 at 5:24 PM, Albert Chan < [hidden email]> wrote:
> You mean just two math.random(0) (128 bits) can predict the next one ?
No, if you see the least significant bit of 128 consecutive calls to
math.random, then you can predict the least significant bit of every
call from there on out.
> Reading http://xoroshiro.di.unimi.it, it seems linearity is not that bad.
> BUT, why Vigna say never use last 2 bits to build double ? I am confused.
The lowerorder bits are less random than the higherorder bits, and
this is true of many RNG designs. If you want a coin flip, pick a bit
out of the middle instead of taking the lowest bit. If you want to
construct a floatingpoint value, the lowest two bits have enough of a
correlation that you get especially bad results.
/s/ Adam


On Mar 23, 2018, at 6:31 PM, Coda Highland < [hidden email]> wrote:
> On Fri, Mar 23, 2018 at 5:24 PM, Albert Chan < [hidden email]> wrote:
>> You mean just two math.random(0) (128 bits) can predict the next one ?
>
> No, if you see the least significant bit of 128 consecutive calls to
> math.random, then you can predict the least significant bit of every
> call from there on out.
>
I misunderstood what Ge were saying, but I somehow got it right !
> two (at most 3) math.random(0) (128 bits) can predict the next one
For math.random(), 3 calls can definitely "crack" xorshift128+
https://blog.securityevaluators.com/hackingthejavascriptlottery80cc437e3b7fToo bad it is not a real lottery :(


> On Mar 23, 2018, at 6:31 PM, Coda Highland < [hidden email]> wrote:
>
> The lowerorder bits are less random than the higherorder bits, and
> this is true of many RNG designs. If you want a coin flip, pick a bit
> out of the middle instead of taking the lowest bit. If you want to
> construct a floatingpoint value, the lowest two bits have enough of a
> correlation that you get especially bad results.
>
> /s/ Adam
>
Do you mean top bits is not as good as the middle bits ?


On Sat, Mar 24, 2018 at 2:25 PM, Albert Chan < [hidden email]> wrote:
>
>> On Mar 23, 2018, at 6:31 PM, Coda Highland < [hidden email]> wrote:
>>
>> The lowerorder bits are less random than the higherorder bits, and
>> this is true of many RNG designs. If you want a coin flip, pick a bit
>> out of the middle instead of taking the lowest bit. If you want to
>> construct a floatingpoint value, the lowest two bits have enough of a
>> correlation that you get especially bad results.
>>
>> /s/ Adam
>>
>
> Do you mean top bits is not as good as the middle bits ?
In some RNGs the bottom bits are weak. In some RNGs the top bits are
weak. The middle is usually safe, so if you don't know the behavior of
the RNG in advance then you should either pull bits out of the middle
or combine bits from both ends. (Obviously if you DO know the RNG's
behavior, pick out what's good.)
/s/ Adam

12
