prev up next   top/contents search

comp.lang.c FAQ list · Question 13.15

Q: I need a random number generator.


A: The Standard C library has one: rand. The implementation on your system may not be perfect, but writing a better one isn't necessarily easy, either.

If you do find yourself needing to implement your own random number generator, there is plenty of literature out there; see the References below or the sci.math.num-analysis FAQ list. There are also any number of packages on the net: old standbys are r250, RANLIB, and FSULTRA (see question 18.16), and there is much recent work by Marsaglia, and Matumoto and Nishimura (the ``Mersenne Twister''), and some code collected by Don Knuth on his web pages.

Here is a portable C implementation of the ``minimal standard'' generator proposed by Park and Miller:

#define a 16807
#define m 2147483647
#define q (m / a)
#define r (m % a)

static long int seed = 1;

long int PMrand()
{
	long int hi = seed / q;
	long int lo = seed % q;
	long int test = a * lo - r * hi;
	if(test > 0)
		seed = test;
	else	seed = test + m;
	return seed;
}
(The ``minimal standard'' is adequately good; it is something ``against which all others should be judged''; it is recommended for use ``unless one has access to a random number generator known to be better.'')

This code implements the generator

X  <-  (aX + c) mod m
for a = 16807, m = 2147483647 (which is 2**31-1), and c = 0.[footnote] The multiplication is carried out using a technique described by Schrage, ensuring that the intermediate result aX does not overflow. The implementation above returns long int values in the range [1, 2147483646]; that is, it corresponds to C's rand with a RAND_MAX of 2147483646, except that it never returns 0. To alter it to return floating-point numbers in the range (0, 1) (as in the Park and Miller paper), change the declaration to
	double PMrand()
and the last line to
	return (double)seed / m;
For slightly better statistical properties, Park and Miller now recommend using a = 48271.

References: K&R2 Sec. 2.7 p. 46, Sec. 7.8.7 p. 168
ISO Sec. 7.10.2.1
H&S Sec. 17.7 p. 393
PCS Sec. 11 p. 172
Knuth Vol. 2 Chap. 3 pp. 1-177
Park and Miller, ``Random Number Generators: Good Ones are Hard to Find''


prev up next   contents search
about this FAQ list   about eskimo   search   feedback   copyright

Hosted by Eskimo North