Re: Bug in math.random() range checking

[albertmcchan <albertmcchan@...>]

On Mar 3, 2018, at 10:01 PM, albertmcchan <albertmcchan@yahoo.com> wrote:

> local rand, RANDMAX = math.random, 0xffff
> local RSIZE = RANDMAX + 1
> 
> function rand_upto(n)   --  return random r, 0 <= r <= n
>     local hi = RSIZE
>     local lo, r = n % hi, 0
>     if lo ~= 0 then
>         while lo * 2 < hi do hi = hi / 2 end   -- minimize rand calls
>         repeat r = rand(0, hi-1) until r <= lo -- remove bias
>     end
>     if lo == n then return r end
>     return rand_upto((n - lo) / RSIZE) * RSIZE + r
> end
> 

Just wanted to comment on above rand_upto(n), for building
an unbiased random number between 0 to n

It is meant as demo.  It should be coded in C, called by math_random.
Using it as is, rand (i.e. math.random) will return result slightly biased.

I did patch my setup (luajit 1.1.8, 32-bits) in C using above idea,
something unexpected happened.

I get unbiased random number(s) without performance penalty !
My guess is it avoided cost of integer to double to integer conversion.

--> patched math.random now return unbiased 31-bit random integer
--> above rand_upto now work properly

luajit does not have 64-bits integer, so above is an overkill.
I can simplify and speedup above for luajit 53-bit "integer" 

function rand_upto(n)         -- return random r = [0, n], n = [0, 0x1p53)
    local lo = n % 1e9           -- split n, max of 2 rand calls
    local r = rand(lo + 1) - 1  -- 0 <= r <= lo
    if lo == n then return r end
    return r + 1e9 * (rand((n - lo) / 1e9 + 1) - 1)
end