Re: Bug in math.random() range checking

[Dirk Laurie <dirk.laurie@...>]

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