[Top][All Lists]

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

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

From: David G Doshay
Subject: Re: [gnugo-devel] rand() % n
Date: Thu, 13 May 2004 10:42:27 -0700

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.


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

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.


gnugo-devel mailing list

reply via email to

[Prev in Thread] Current Thread [Next in Thread]