From: mert0407 AT sable DOT ox DOT ac DOT uk (George Foot)
Newsgroups: comp.os.msdos.djgpp
Subject: Re: Random numbers/George
Date: 3 Jun 1997 20:39:55 GMT
Organization: Oxford University, England
Lines: 65
Message-ID: <5n1ver$gn9@news.ox.ac.uk>
References: <2 DOT 2 DOT 32 DOT 19970603165722 DOT 006d12ec AT gate>
NNTP-Posting-Host: sable.ox.ac.uk
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp
Precedence: bulk

Alan Wilson (awilson AT wilshire DOT com) wrote:
: At 01:46 AM 6/3/97 GMT, you wrote:
: >Chris Mangum and Savanna Judd (sneeches AT cruzio DOT com) wrote:
: >
: >: Try using this:
: >
: >: 	srand(time(NULL));
: >
: >This will seed the rand() generator; to seed the random() generator,
: >replace `srand' with `srandom'.
: >
: >-- 
: >George Foot <mert0407 AT sable DOT ox DOT ac DOT uk>

: But will it give TRUE random Numbers????

Define a `true' random number. Apparently, random() is a `more' random
generator than rand(); presumably the reason the portable rand() function
uses a worse generator is that the algorithm is specified in the standard,
although I really don't know (does anyone?).

If you have Knuth's series of books, `The Art of Computer Programming',
volume 2 (`Seminumerical Algorithms') deals in great depth with the
generaion of random numbers and ways to test their randomness. At one
stage I meant to run these tests on the two, and on ways of restricting
the generated numbers to a smaller range, but I never got around to it.

Apparently (I'm not sure where I picked up this information), the
generator used in random() is guarranteed also to produce a good random
sequence for any combination of bits, i.e. you can mask out a single bit,
or two bits, or any number, and the sequence (restricted to those bits)
will be a good random sequence. AFAIK this isn't true for rand().

I'm not sure if the above implies that random()%x is a good generator of
numbers in the range (0,x-1) for x not equal to a power of 2; I haven't
thought much about it. The tests I mentioned would answer this.

Knuth's books are quite expensive, so if you want to persue this further I
suggest you try to borrow a copy, or go to a library. I was lucky enough
to be given the first two volumes. Sometime I may get around to
implementing these tests (there are about 10 IIRC, and each isn't very
complicated), but I have exams coming up so it may not be soon.

If you want some idea of the sorts of tests performed, their purpose is to
ensure that the probabilities of obtaining each number in the range are
equal at all times. These tests include (IIRC):

* Frequency testing on the numbers (in the long term they should all occur
similar numbers of times)

* Frequency tests on sequences of numbers

* Checking that, after getting number X, the number of attempts before the
next X follows the expected distribution (Poisson I believe)

* Chi squared testing

... and quite a few others.

If you (or anyone) does perform these tests or others, I'd be interested
to know the results.

-- 
George Foot <mert0407 AT sable DOT ox DOT ac DOT uk>
Merton College, Oxford