Re: Bug in math.random() range checking

On Mar 3, 2018, at 6:45 PM, Bruce Hill <bruce@bruce-hill.com> wrote:

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

Does the do while loops guaranteed finite ?
If yes, how many loops do you expect ?

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

I would suggest you track count of rand() calls.

Looking at the code, it seems to require many, many calls.

If rand() return 16 bits, inner while loop call max of 4 times.

Throwing away all 4 rand calls if outer loop fail seems wasteful.

What is the chances of max_r == target_max_r ?

It just feel the code is doing too much at once.

And, I am not so sure it is correct (at least about the 50% chance)

I suggest move the code as function rand_upto(), and

have math_random() return low + rand_upto(high - low)

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