[Top][All Lists]

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

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

From: Gunnar Farnebäck
Subject: Re: [gnugo-devel] rand() % n
Date: Fri, 07 May 2004 20:32:40 +0200
User-agent: EMH/1.14.1 SEMI/1.14.3 (Ushinoya) FLIM/1.14.2 (Yagi-Nishiguchi) APEL/10.3 Emacs/21.3 (sparc-sun-solaris2.9) MULE/5.0 (SAKAKI)

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

/* 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?


reply via email to

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