Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!sdd.hp.com!elroy.jpl.nasa.gov!decwrl!deccrl!news.crl.dec.com!nntpd.lkg.dec.com!netrix.nac.dec.com!lan_csse
From: lan_csse@netrix.nac.dec.com (CSSE LAN Test Account)
Newsgroups: comp.unix.questions
Subject: Re: bad random generation
Keywords: random
Message-ID: <22896@shlump.lkg.dec.com>
Date: 24 May 91 15:54:22 GMT
References: <3262@bimacs.BITNET> <3927@motcsd.csd.mot.com>
Sender: news@shlump.lkg.dec.com
Organization: Digital Equipment
Lines: 82

>yedidya@bimacs.BITNET (Yedidya Israel) writes:
>>        Recently I used the random generator  random()  with the default
>>seed to generate input for sorting programs.  While scanning the results,
>>I noticed two pairs of very close numbers in the output.  When I then
>>reviewed the input, I was disturbed to find that these numbers came from
>>nearby positions in the input list, in positions 26 and 29, 27 and 30,
>>respectively.  Since I am not an expert in random number generation, I
>>should appreciate your reaction.

In addition to the Knuth books, here is a routine that I've been passing
around for some time.  You might install it in your libraries in place of
the rand() routine; for your own applications, you can just call minrand()
directly.  There are probably lots more around...

 - - - - - - - - - - - - C U T - H E R E - - - - - - - - - - - - - - - - - - -
/*		minseed(s);
**		i = minrand();
** This is the "minimal standard random" routine by Stephen K. Park and Keith
** W. Miller, in "Random number generators: good ones are hard to find", in
** the Oct 1988 CACM (v.31, no.10).  The authors make a good case that this
** is the minimally-acceptable pseudorandom-number generator, as it is highly
** random by all common statistical tests, and has a sufficiently long period
** (2 ^ 31 - 2) for almost all applications.  They suggest installing in in
** all libraries in place of the (usually deficient) routines supplied by most
** vendors, and to use an alternate routine only if it is KNOWN to be better.
**
** You are encouraged to give this source code to anyone who wants it.  There
** is no copyright.  It was typed in by John Chambers in C while reading the
** above article, and I don't think the authors will make any claims on the
** code as long as we continue to give them credit.
**
** This version returns a long int in the range [1..2147483646].
**
** Any int in the range [1..2147483646] may be used as a seed.  To get a unique
** sequence, use an initialization like minseed(getpid()) or minseed(time(0L)).
** For a reproducible sequence, ask the user for a seed, and encourage them to
** use something memorable like their Social Security number.  Do not use zero,
** as the result will be a sequence of all zeroes.  Note that the upper bound
** is 0x7FFFFFFE, which you may find easier to type.
**
** If compiled with -DTEST, a test driver is compiled that performs the check 
** they suggest of starting with seed=1, calculating 10,000 random numbers, 
** and verifying the resulting seed.  I'd suggest running the test program
** via the command:
**		time minrand
** and dividing the results by 10,000.  This gives you approximately the time
** to make one minrand() call.
*/
#define A 16807			/* Multiplier */
#define M 2147483647	/* Modulus */
#define Q 127773		/* M / A */
#define R 2836			/* M % A */

static seed = 1;

minseed(s) long s; { seed = s; }

long
minrand()
{	long lo, hi, test;

	hi = seed / Q;
	lo = seed % Q;
	test = (A * lo) - (R * hi);
	seed = (test > 0)? test: test + M;
	return seed;
}
#ifdef TEST
#include <stdio.h>
#define testseed 1043618065	/* Seed 10,001 */

main()
{	int n;

	for (n=1; n<=10000; n++)
		minrand();
	if (seed == testseed)
		 fprintf(stderr,"The 10,001st seed is correct: %ld.\n",seed);
	else fprintf(stderr,"The 10,001st seed is incorrect: %ld.\n",seed);
	exit(seed != testseed);
}
#endif