Re: Bug in math.random() range checking

[Bruce Hill <bruce@...>]

> On Mar 1, 2018, at 4:31 AM, Roberto Ierusalimschy <roberto@inf.puc-rio.br> wrote:
> 
>>>>  luaL_argcheck(L, up - low + 1 <= L_RANDMAX, 1, "interval too large");
>> 
>> up - low isn't representable when the difference is greater than
>> LUA_MAXINTEGER.
> 
> we have to cast all operands to LUA_UNSIGNED.
> 
> -- Roberto

Good catch and good suggestion. I believe this is correct version of what I originally proposed:

    luaL_argcheck(L, (lua_Unsigned)up - (lua_Unsigned)low <= (lua_Unsigned)L_RANDMAX, 1, "interval too large");

> On Mar 1, 2018, at 4:37 AM, Albert Chan <albertmcchan@yahoo.com> wrote:
> 
> I am not so sure the original version is wrong, since it does
> not claim that all bits returned must be random, it just check
> if the interval is too large (with lua integer). If the error message
> were "not all bits are random", the patch make sense.

I think the original version is wrong because the math.random() documentation says: "... math.random returns a pseudo-random integer with uniform distribution in the range [m, n].", but the original code doesn't produce a uniform distribution in the range [m, n]. For example, math.random(2^32-1) only returns even numbers, which is not a uniform probability distribution over the integers in [0, 2^32-1] and is also very counterintuitive.

When I originally encountered this behavior, it took me a while to debug it and realize Lua was responsible for the weirdness (rather than my code), and further digging in Lua's source code to figure out why. I don't think anyone else should have to go through that process, so it would be nice to produce a helpful error message instead of silently doing something unexpected and undocumented. Either that, or have the C code support generating uniform random distributions for all integer ranges. I've written and tested a version that does this, but it's a bigger change than my original proposal, and it introduces some complexity, so I can understand if people are reluctant to make the bigger change (though I am pretty happy with this code!). Here's the change:

***************
*** 247,275 ****
  static int math_random (lua_State *L) {
!   lua_Integer low, up;
!   double r = (double)l_rand() * (1.0 / ((double)L_RANDMAX + 1.0));
    switch (lua_gettop(L)) {  /* check number of arguments */
      case 0: {  /* no arguments */
        lua_pushnumber(L, (lua_Number)r);  /* Number between 0 and 1 */
        return 1;
      }
      case 1: {  /* only upper limit */
        low = 1;
!       up = luaL_checkinteger(L, 1);
        break;
      }
      case 2: {  /* lower and upper limits */
        low = luaL_checkinteger(L, 1);
!       up = luaL_checkinteger(L, 2);
        break;
      }
      default: return luaL_error(L, "wrong number of arguments");
    }
!   /* random integer in the interval [low, up] */
!   luaL_argcheck(L, low <= up, 1, "interval is empty");
!   luaL_argcheck(L, low >= 0 || up <= LUA_MAXINTEGER + low, 1,
!                    "interval too large");
!   r *= (double)(up - low) + 1.0;
!   lua_pushinteger(L, (lua_Integer)r + low);
    return 1;
  }

--- 247,295 ----
  static int math_random (lua_State *L) {
!   lua_Integer low, high;
    switch (lua_gettop(L)) {  /* check number of arguments */
      case 0: {  /* no arguments */
+       double r = (double)l_rand() * (1.0 / ((double)L_RANDMAX + 1.0));
        lua_pushnumber(L, (lua_Number)r);  /* Number between 0 and 1 */
        return 1;
      }
      case 1: {  /* only upper limit */
        low = 1;
!       high = luaL_checkinteger(L, 1);
        break;
      }
      case 2: {  /* lower and upper limits */
        low = luaL_checkinteger(L, 1);
!       high = luaL_checkinteger(L, 2);
        break;
      }
      default: return luaL_error(L, "wrong number of arguments");
    }
!   /* 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;
  }

Attachment: signature.asc
Description: Message signed with OpenPGP