[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
- Subject: Re: Bug in math.random() range checking
- From: Dirk Laurie <dirk.laurie@...>
- Date: Sat, 3 Mar 2018 15:48:04 +0200
Lua's math library is as good as the one that comes with your C
compiler. If your compiler is Posix-compliant, only 31 bits are random
because that is the Posix standard.
The astonishing thing is that we have knowin since 1976 how to turn a
bad random number generator into a good one, this method made it into
the second edition (1981) [1] of Donald Knuth's well known and highly
respected Art of Computer Programming, Volume 2 as Algorithm B on p32
— and most random number generators of most programming languages
still suck.
If your application requires high-quality pseudo-random numbers, I
strongly urge you to implement that algorithm. Here it is in Lua.
do -- closure
local X = {}
local Y
local rand = math.random
local function rand53() -- integers in the range 0..(1<<53)-1
return (rand(0,(1<<26)-1)<<27)+rand(0,(1<<27)-1)
end
function randB(init)
if init then -- initialize
for k=0,255 do X[k]=rand53() end
Y = rand53()
end
j = Y>>45 -- high-order 8 bits
Y = X[j]
X[j] = rand53()
return Y
end
end -- closure
2018-03-03 14:24 GMT+02:00 Albert Chan <albertmcchan@yahoo.com>:
> On Mar 3, 2018, at 4:33 AM, Bruce Hill <bruce@bruce-hill.com> wrote:
>
>> ! /* random integer in the interval [low, high] */
>> ! luaL_argcheck(L, low <= high, 1, "interval is empty");
>> ! lua_Unsigned r, max_r; /* max_r tracks the maximum value that "r" could currently be */
>> ! lua_Unsigned target_max_r = (lua_Unsigned)high - (lua_Unsigned)low;
>> ! do {
>> ! r = 0u, max_r = 0u;
>> ! do { /* Concatenate chunks of random bits onto r until r could be >=target_max_r */
>> ! /*
>> ! ** Multiplying unsigned values by L_RANDMAX+1u is equivalent to left shifting by the
>> ! ** number of random bits returned by l_rand(), since L_RANDMAX+1u is always a power of 2.
>> ! ** (Unless L_RANDMAX+1u overflows to 0, but in that case, the loop will exit on the
>> ! ** first iteration because max_r = ((0u * 0u) | -1u) guarantees max_r >= target_max_r)
>> ! */
>> ! r = (r * (L_RANDMAX + 1u)) | l_rand();
>> ! max_r = (max_r * (L_RANDMAX + 1u)) | L_RANDMAX;
>> ! } while (max_r < target_max_r);
>> ! /* If r is in exactly the range we need, it won't have bias and we can use it. */
>> ! if (max_r == target_max_r) {
>> ! lua_pushinteger(L, (lua_Integer)((lua_Unsigned)low + r));
>> ! return 1;
>> ! }
>> ! /* Otherwise, retry if r % (target_max_r+1u) would be biased towards 0 */
>> ! } while (r >= max_r - (max_r % (target_max_r + 1u)));
>> !
>> ! r %= target_max_r + 1u; /* this will not overflow, since target_max_r < max_r */
>> ! lua_pushinteger(L, (lua_Integer)((lua_Unsigned)low + r));
>> return 1;
>> }
>
> 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 ?
>
> What does lua doc say about math.random with no argument ?
>
> On my machine, math.random() only have 16 bits randomness.
> (will be nice if all 53 bits are random)
>