Re: The probability of returning zero by math.random is doubled.

[Mike Pall <mikelu-0809@...>]

Dave Dodge wrote:
> On Fri, Sep 19, 2008 at 03:09:49PM +0200, Dirk Feytons wrote:
> > On Fri, Sep 19, 2008 at 12:58 PM, G? Weijers <ge@weijers.org> wrote:
> > [...]
> > > My favorite is the 'Well' generator
> > > http://www.iro.umontreal.ca/~panneton/WELLRNG.html
> > 
> > Bob Jenkins' ISAAC (http://burtleburtle.net/bob/rand/isaacafa.html)
> > appears to be quite good, assuming of course it is seeded properly.
> > It's also in the public domain.
> 
> Another popular one is the Mersenne Twister, which I've seen credited
> many times in console games.  The stock implementation used to be GPL
> but is now BSD, and there are several Lua implementations/hooks
> including "Numeric Lua" over at LuaForge and "lrandom" from lhf (who
> has already replied in this thread :-)
> 
> http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html
> http://en.wikipedia.org/wiki/Mersenne_Twister

Don't forget about the Tausworthe generators. They can provide
long periods with a small amount of state space:

   http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme2.ps

I was thinking about using them for the random number generator in
LJ2. Since this needs to generate 52 bits for doubles (using the
mask and subtract 1.0 trick) and since LJ2 needs 64 bit ints
anyway, I've considered using one of these two:

- table 3, 1st entry, period 2^223, 32 bytes of state
- table 6, 1st entry, period 2^258, 40 bytes of state

Implementation of the first one (public domain, if anyone cares):

#define TW64(z, k, q, s) \
  ((((z) & (uint64_t)(-1LL<<(64-(k)))) << (s)) ^ \
   ((((z) << (q)) ^ (z)) >> ((k)-(s))))

static uint64_t tw223_step(uint64_t *st)  /* Pass a uint64_t state[4] */
{
  uint64_t z, r;
  z = st[0]; z = TW64(z, 63, 31, 18); r = z; st[0] = z;
  z = st[1]; z = TW64(z, 58, 19, 28); r ^= z; st[1] = z;
  z = st[2]; z = TW64(z, 55, 24,  7); r ^= z; st[2] = z;
  z = st[3]; z = TW64(z, 47, 21,  8); r ^= z; st[3] = z;
  return r;
}

Given the constraints for standard Lua, the 32 bit generators from
table 1 with period 2^113 and 16 bytes of state look like a good
choice (just pick the first set of parameters). But have a look at
the paper for the special seeding requirements.

--Mike