Re: Bug in math.random() range checking

On Mar 3, 2018, at 10:37 AM, Roberto Ierusalimschy <roberto@inf.puc-rio.br> wrote:

We are considering xorshift128+ for Lua 5.4, so that we can have 64 bits
of randomness.

I think this would be the best long-term solution, but if there's going to be a 5.3.5 bugfix release, I'd recommend including either of the patches I suggested. Also, if you're upgrading Lua's RNG, it would be nice to allow users to instantiate multiple random generators with different seeds (like Python's random.Random()). It's very useful for game development, and right now you need to use third party RNG implementations like love.math.newRandomGenerator().

On Mar 3, 2018, at 4:24 AM, Albert Chan <albertmcchan@yahoo.com> wrote:

Is that modified Paul Hsieh code ?
http://www.azillionmonkeys.com/qed/random.html

Does the do while loops guaranteed finite ?
If yes, how many loops do you expect ?
...
On my machine, math.random() only have 16 bits randomness.
(will be nice if all 53 bits are random)

It's not modified Paul Hsieh code. I remembered the basic modulus/bias concept from a long time ago, and looked at some stackoverflow discussions a bit before implementing my version. The inner do-while loop is guaranteed to run in exactly as many steps as it takes to generate enough bits for your random number. E.g. random(0, 2^16-1) will loop once if your platform produces 16 bits of randomness per call to l_rand(), and random(0, 2^35-1) will loop three times (16+16+16 = 48 >= 35). The outer do-while loop is not guaranteed to be finite, but it has a strictly less than 50% chance of repeating the loop each time (and will typically be much less likely), so the expected number of outer loops in the worst case is <2 (and for most inputs, closer to 1).

What does lua doc say about math.random with no argument ?

It says: "When called without arguments, returns a pseudo-random float with uniform distribution in the range [0,1)." I kept the existing implementation for simplicity, which uses one call to l_rand() and squashes that into [0,1). Ideally, more bits of randomness would be better, but the existing behavior here is not as much of a problem, because you normally program a bit more defensively around floating point numbers, knowing that they have limited precision and are just an approximation of Reals. If you wanted to add enough bits of randomness to fill the mantissa of an IEEE 754 floating point number, you can do something like:

lua_Unsigned max_mantissa, r = 0, max_r = 0;

/* With IEEE 754, -inf has 0's in all the mantissa bits and 1's everywhere else */

*(lua_Number*)&max_mantissa = -1.0/0.0;

max_mantissa = ~max_mantissa;

do {

r = (r * (L_RANDMAX + 1u)) | l_rand();

max_r = (max_r * (L_RANDMAX + 1u)) | L_RANDMAX;

} while (max_r < max_mantissa);

lua_pushnumber(L, (lua_Number)r / ((lua_Number)max_r + 1.0));

return 1;

(Or, if you wanted to get really hacky and avoid floating point division, you could randomize the mantissa, copy the sign/exponent bits from 1.0 to get a number in [1.0,2.0), then subtract 1.0 and get a similar result to the above code)