Re: [gnugo-devel] rand() % n

[Douglas Ridgway]

Hi Gunnar!

On Fri, 7 May 2004, Gunnar Farnebäck wrote:

> Douglas wrote:
> > Some random number generators have low order bits which are less random
> > than the high order bits. Since modulo picks out the low order bits, it
> > may not be the best way to generate a random integer in a given range. I
> > don't know whether this is a concern for GnuGo's generator,
> 
> It is not a concern. As documented in utils/random.c, GNU Go uses this
> generator:
> 
> /* This is an implementation of the TGFSR (twisted generalized
>  * feedback shift register) random number generator TT800, which was
>  * published in:
> 
> The generators which have problems with the low order bits are much
> less sophisticated than this one, and the tests shown in the paper
> confirm that we do not need to worry about the distribution of
> specific bits.

Hm, all I can find is stuff about the leading bits, and how far down good 
properties extend. 

> > +unsigned int
> > +gg_nrand(unsigned int n)
> > +{
> > +  return (unsigned int) (1.0*n*next_rand()/(0xffffffff+1.0));
> >  }
> 
> Now *this* makes me nervous. Are you completely certain that this
> implementation would never return n?

I took this construction from Numerical Recipes, but it also appears on my
rand(3) man page (quoting from NR). That doesn't mean it's right, of
course. One concern is overflow in the denominator. I think it has to be
computed double precision: 52 bits is enough to hold 2^32, 23 is not.

doug.
address@hidden