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
I tried rand_upto(1e18), rand calls average around 4 ... not bad