Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!decwrl!elroy.jpl.nasa.gov!jarthur!nntp-server.caltech.edu!laguna.ccsf.caltech.edu!daveg From: daveg@near.cs.caltech.edu (Dave Gillespie) Newsgroups: comp.lang.c Subject: Re: random() error in Turbo C++ Message-ID: Date: 9 Sep 90 08:20:53 GMT References: <118662@linus.mitre.org> <17607@haddock.ima.isc.com> <1990Sep8.201520.15916@diku.dk> Sender: news@laguna.ccsf.caltech.edu Organization: California Institute of Technology Lines: 51 In-Reply-To: njk@diku.dk's message of 8 Sep 90 20:15:20 GMT >>>>> On 8 Sep 90 20:15:20 GMT, njk@diku.dk (Niels J|rgen Kruse) said: > karl@haddock.ima.isc.com (Karl Heuer) writes: >> ... do r = rand() / ((RAND_MAX + 1UL) / n); while (r >= n); ... > This require 2 divisions however. Here is an algorithm, that > only require one division: > ... do { > res = (sor = rand()) % n; > sor = RAND_MAX - (sor - res); > } while (sor < n-1); ... Most rand() implementations use linear congruential random number generators, which are notorious for having unpleasant properties in their low bits. Experts recommend always dividing instead of mod'ing, so that you are using the high bits of the result of rand(). A linear congruential generator uses the formula x = (a*x + c) % (RAND_MAX+1L) to generate a sequence of pseudo-random numbers; the first "x" is the seed you supply to srand(). The numbers "a" and "c" are chosen according to a black art you can read about in Knuth or elsewhere. "RAND_MAX" is chosen so that "RAND_MAX+1" is a power of two; this makes the modulo operation cheap in binary. Consider the least significant bit of "x", i.e., whether or not "x" is even or odd, as this formula is applied to it: The binary "%" doesn't affect this bit; adding "c" either inverts this bit or leaves it the same; multiplying by "a" either clears this bit or leaves it the same. So no matter what the values of "a", "c", and "RAND_MAX", the low bit of your "random" sequence will be extremely non-random. It turns out that only the most-significant bits of "x" really act like good random numbers. Sometimes rand() will tweak its results to be less blatantly bad in the low bits, but every one I've seen was ultimately linear congruential. A couple of convenient references: Knuth's _Art of Computer Programming_, volume II; _Numerical Recipes_ by Press et al, chapter 7. -- Dave -- Dave Gillespie 256-80 Caltech Pasadena CA USA 91125 daveg@csvax.cs.caltech.edu, ...!cit-vax!daveg