From: gfoot AT mc31 DOT merton DOT ox DOT ac DOT uk (George Foot)
Newsgroups: comp.os.msdos.djgpp
Subject: Re: a randomize function for DJGPP?
Date: 7 Mar 1997 20:01:11 GMT
Organization: Oxford University
Lines: 44
Message-ID: <5fps67$pc3@news.ox.ac.uk>
References: <5flbpp$m74 AT nr1 DOT ottawa DOT istar DOT net> <331FC0D1 DOT 1A26 AT cs DOT com> <E6oqJs DOT K2n AT boss DOT cs DOT ohiou DOT edu>
NNTP-Posting-Host: mc31.merton.ox.ac.uk
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp

Dave Cigna (cigna AT helios DOT phy DOT OhioU DOT Edu) wrote:

: The numbers will still not be uniformly distributed. Smaller values are
: more likely than large ones. To understand why, remember that random()
: and rand() return an integer between 0 and RAND_MAX. Suppose, just for
: the sake of argument, that RAND_MAX == 5 and you want random numbers
: from 0 to 3. Then random()%4 will evaluate to 1 when random() returns
: *either* 1 or 5, but the only way to get a 3 is for random() to return
: exactly 3. In other words 0 and 1 are twice as likely to occur as 2 and 
: 3 in this case. Even with a large RAND_MAX (like 2^31), the numbers at
: the small end of (0,X) will be more likely than those at the high end.

For the record, random() returns numbers from 0 to MAXINT, which is one
less than power of two. It also guarrantees that *any* bit combination
you choose will return a uniformly random distribution; e.g. random()&5
will give numbers from {0,1,4,5} with a uniform distribution.

Admittedly, using '%' with a number which is not a power of two will 
give slightly more low numbers than high, but...

: The best way to get get random numbers uniformly distributed from
: 0 to X-1 is to use:

:   n = ((double)random() / RAND_MAX) * X;

: If you want to cast n to an int, that's your business.

... this is no better. For example, suppose that MAXINT were 4, and you 
set X to be 3. Then n would be one of {0.0,0.75,1.5,2.25}, and when cast
to int this becomes {0,0,1,2} which is the same result as random()%3.

This is getting pedantic, but you cannot (simply) get a truly random 
distribution over X numbers from a random function returning one of
2^n numbers. I say simply; one solution is to keep taking random() until
the value is in the range you want. A more efficient technique is to keep
taking random()&Y until it is in the required range, with Y=2^n-1 such
that Y>=X-1.

In practise, though, MAXINT and RAND_MAX are so high that it doesn't 
really matter.

-- 
George Foot <gfoot AT mc31 DOT merton DOT ox DOT ac DOT uk>
Merton College, Oxford.