Re: Bug in math.random() range checking

[Albert Chan <albertmcchan@...>]

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)