Mail Archives: djgpp/1997/03/09/03:55:41
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.
- Raw text -