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

[Gunnar Farnebäck]

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:
 *
 * Matsumoto, M. and Kurita, Y.: Twisted GFSR generators II.
 * ACM Transactions on Modeling and Computer Simulations,
 * Vol 4, No. 3, July 1994, pp 254--266
 *
 * The generator produces a pseudo-random sequence of 32 bit integers
 * with period 2^800 - 1 and is reported to have excellent
 * equidistribution properties, as well as being fast.
 */

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.

> but it makes me nervous anyway. Here's a patch:
> [...]
> +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?

/Gunnar