random() error in Turbo C++

[Dave Gillespie]

>>>>> On 8 Sep 90 20:15:20 GMT, njk at diku.dk (Niels J|rgen Kruse) said:

> karl at 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 at csvax.cs.caltech.edu, ...!cit-vax!daveg