lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]


It would be good if the mapping of the output of 'rand' would preserve any good underlying properties of 'rand'. Lua's 'math.random' does not, the value 0 is twice as likely as any other. The problem is that 'rand' produces values inclusive of 'RAND_MAX'. Dividing by 'RAND_MAX +1' is not the solution, because RAND_MAX may be equal to 'INT_MAX', so 'RAND_MAX+1' may cause an integer overflow.

You could do something like:

lua_Number r;
do {
	r = rand() / (RAND_MAX+1.0);
}while(r >= 1.0); // SunOS hack

In general it's a bad idea to use 'rand' for anything critical, it is usually implemented as a simple linear congruential generator, which have terrible properties. Much better generators exist. My favorite is the 'Well' generator

http://www.iro.umontreal.ca/~panneton/WELLRNG.html

Gé

On Sep 18, 2008, at 2:12 AM, Mark Meijer wrote:

There I go again... I proposed floor(r*u+.5) because I assumed that a
call to math.random with one argument implies a lower bound of 0.
Instead this implied lower bound is 1, so I was (again) wrong. Also I
won't talk anymore about the statistical properties, because basically
the Lua manual explicitly states it does not guarantee any.

So just ignore me, and appologies for the noise :S


2008/9/18 Mark Meijer <meijer78@gmail.com>:
Doh... Correction to my first post: The value range of 'r' is never
inclusive of 1, even if rand() is inclusive of RAND_MAX, and that's
due to the modulo RAND_MAX operation (in the original code). So my
previous post can largely be ignored.

Although it does mean the modulo is needed not only for the mentioned
SunOS issue (and therefore it does not preserve the statistical
properties of rand() on any platform, as mentioned by OP).

And, I still think the "floor(r*u)+1" calculation does NOT preserve
the statistical properties of whatever rand() returns, and should
instead be "floor(r*u+.5)" (e.g. consider the case when r*u == .4, I
believe that should be rounded to 0 instead of 1).

Cheers.

2008/9/18 Mark Meijer <meijer78@gmail.com>:
The manual does state that "No guarantees can be given for its
statistical properties." I'm no maths expert, but this seems
especially true if rand can indeed return values greater than
RAND_MAX, as is claimed for SunOS (unless its range is exactly a
multiple of RAND_MAX).

When I looked at the relevant code in lmathlib.c, though, something
else occured to me. For reference, here is that code:

---------->8----------
static int math_random (lua_State *L) {
/* the `%' avoids the (rare) case of r==1, and is needed also because on some systems (SunOS!) `rand()' may return a value larger than RAND_MAX */
lua_Number r = (lua_Number)(rand()%RAND_MAX) / (lua_Number)RAND_MAX;
switch (lua_gettop(L)) {  /* check number of arguments */
  case 0: {  /* no arguments */
    lua_pushnumber(L, r);  /* Number between 0 and 1 */
    break;
  }
  case 1: {  /* only upper limit */
    int u = luaL_checkint(L, 1);
    luaL_argcheck(L, 1<=u, 1, "interval is empty");
    lua_pushnumber(L, floor(r*u)+1);  /* int between 1 and `u' */
    break;
  }
  case 2: {  /* lower and upper limits */
    int l = luaL_checkint(L, 1);
    int u = luaL_checkint(L, 2);
    luaL_argcheck(L, l<=u, 2, "interval is empty");
lua_pushnumber(L, floor(r*(u-l+1))+l); /* int between `l' and `u' */
    break;
  }
  default: return luaL_error(L, "wrong number of arguments");
}
return 1;
}
----------8<----------

Firstly, the range returned by math.random() is stated in the manual
to be in the range [0,1) which (I believe) means  the 1 is exclusive
(i.e. it should never actually return 1). I think in the range from C
rand() the RAND_MAX is inclusive. So, the (original) scaling
calculation done in lmathlib.c tells me math.random() can actually
return 1. OP's patch prevents this, although I don't believe that
patch is an improvement to the statistical properties of the returned
value. I believe the original calculation preserves the statistical
properties of whatever is returned by rand(), except for the SunOS
issue. But again, I'm no maths expert.

Secondly, when arguments are passed to math.random to indicate a
desired range, according to the manual, the returned value is
inclusive of both the min and max value of that range. But due to the first issue, the returned value could potentially exceed the requested
maximum value, by 1 (i.e. in case 1, if r==1 and u==1 then
floor(1*1)+1 == 2). This is fixed if the range of 'r' is made to be
exclusive of 1. Although, to improve it's statistical properties, the
calculation should rather be "floor(r*u+.5)", I think.

Cheers


2008/9/18 Atry <pop.atry@gmail.com>:
In math_random(), whether rand() returns 0 or RAND_MAX, the result of
math_random() would be 0. It should modulo RAND_MAX + 1 instead of
modulo RAND_MAX.

--- lua-5.1.4/src/lmathlib.c
+++ lua-5.1.4/src/lmathlib.c
@@ -181,7 +181,7 @@ static int math_max (lua_State *L) {
static int math_random (lua_State *L) {
/* the `%' avoids the (rare) case of r==1, and is needed also because on some systems (SunOS!) `rand()' may return a value larger than RAND_MAX */ - lua_Number r = (lua_Number)(rand()%RAND_MAX) / (lua_Number)RAND_MAX;
+  lua_Number r = (lua_Number)(rand()%(RAND_MAX + 1)) /
(lua_Number)(RAND_MAX + 1);
 switch (lua_gettop(L)) {  /* check number of arguments */
   case 0: {  /* no arguments */
     lua_pushnumber(L, r);  /* Number between 0 and 1 */




--
Gé Weijers
ge@weijers.org