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

[David G Doshay]

As a physics guy who does Monte Carlo simulations, where the quality
of the random number generator (RNG) is a real issue, I am wondering:

How often is the RNG called in Gnu Go?

I am having a problem imagining that the specific details of the RNG
are really important. It seems that most any reasonable RNG, even
a simple and direct linear congruential generator with "proper"
parameters, should be fine.

I have used a linear congruential generator with shuffle (also from
Numerical Recipes), but they take a little more memory to hold the
shuffle stack and require two calls to the LCG to get one random
number, one to select the output from the shuffle stack and another
to refill that stack location. My simulations would have shown any
bias or correlation in the RNG, and there were none.

The concern about overflow issues I completely understand.

Cheers,
David


On May 12, 2004, at 4:50 PM, Gunnar Farnebäck wrote:

> Douglas wrote:
> > > 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.
>
> Hm, the paper is more difficult to get into than I remembered and it's
> not quite clear to me now exactly what the equidistribution properties
> mean. However, just the fact that it even managed to get published in
> a journal at that time is indication enough for me that it's extremely
> unlikely to have any glaring problems like short periods for the low
> order bits.
>
> > 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.
>
> I'm sure it's good advice if there is a risk that the random number
> generator you use is an old linear congruence generator, but otherwise
> I'm pretty sure it's just a waste of time to get into those
> floating-point operations.
>
> > 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.
>
> You can overflow in the numerator as well. If n is very big even 52
> bits won't be enough.
>
> /Gunnar
>
>
> _______________________________________________
> gnugo-devel mailing list
> address@hidden
> http://mail.gnu.org/mailman/listinfo/gnugo-devel