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

[Gunnar Farnebäck]

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