Re: Bug in math.random() range checking

[albertmcchan <albertmcchan@...>]

Below is rand_upto(n) that work without patching any c code.

It call math.random() instead of math.random(0, hi), avoiding bias.

I made an error earlier. On my machine, RAND_MAX = 0x7fff

local rand, floor = math.random, math.floor

local RSIZE = 2 ^ 15  -- RAND_MAX + 1

function rand_upto(n)  -- return random r, 0 <= r <= n

    local hi = RSIZE

    local lo, r = n % hi + 1, 0

    if lo > 1 then

        while lo + lo < hi do hi = hi / 4 end   -- reduce rand calls

        if lo >= hi then hi = hi * 2 end        -- scaled too far

        repeat r = rand() * hi until r < lo    -- remove bias

    end

    if lo > n then return floor(r) end

    return floor(r) + RSIZE * rand_upto((n - lo) / RSIZE)

end