long mrandom(m) long m; double frandom() int init_rng(seed, filename) long seed; char *filename; int save_rng(filename) char *filename; int restart_rng(filename) char *filename; void reconstruct_rng(seed, count1, count2) long seed; long count1; long count2; char *describe_rng(rngid) char rngid[RNGIDSTRLEN];
mrandom(m) generates random integers in the range 0 to m-1, using a call to the 4.3bsd random() function. This is a non-linear additive feedback random number generator. The main advantage of mrandom(m) over random() is that you can save the complete state of the random number generator to a disk file, for later continuation of the same pseudorandom sequence. The period of mrandom(m)'s pseudorandom output is thus guaranteed to be long. In contrast, random()'s period can be quite short if you repeatedly save and restore its state using setstate(), because some of random()'s state is private.
To use mrandom(), you must first initialize the random number generator. The easiest way to do this is to make a call to init_rng(seed, filename). If all goes well, this call will return the value 1, indicating that a file has been created describing the initial state of your generator. Hereafter, this file will be called an RNG state file.
init_rng will perform some error checks on the RNG state file after it is written, returning the value 0 if a problem is detected.
After an init_rng(seed, filename) call, the random number generator is in the same state as it would be if you had directly called srandom(seed) or initstate(seed, state, 128) on a ``fresh'' copy of the random() code.
Warning: do not write your own calls to srandom(), initstate(), random(), or setstate() if you are using the mrandom package. If you do so, the long-period advantages of mrandom will be lost, and a later call to save_rng or restore_rng may fail.
It is good experimental practice to preserve copies of your RNG state files, in case you ever want to reproduce a result. The state file is ASCII text, so it is portable across systems.
Another good experimental practice is to ``stamp'' each printout with a record of the initial RNG state. You can do this by including a copy of the RNG state file, although this is a dozen lines long and a few hundred characters. A more convenient method is to use a call to describe_rng(rngid). This puts a one-line short-form of the current RNG state in the character string rngid.
describe_rng(rngid) returns the value of rngid, for convenience. To print this short-form RNG descriptor, for example, you can execute printf(describe_rng(rngid)). Note: you must declare storage for rngid in your own program with a declaration such as char rngid[RNGIDSTRLEN]. RNGIDSTRLEN is defined with the value 80 in the current release of mrandom.
The short-form description provided by describe_rng can be used, at a later date, to reconstruct the state of the RNG. This can be a slow process, since it involves seeding a virgin copy of the random() generator, then calling random() a number of times. The relevant call in the mrandom package is reconstruct_rng(seed, count1, count2), where seed is the initial seed, count1 is the total number of calls to random() since initialization, mod one billion, and count2 is a ``div one billion'' counter.
I hope you never have occasion to call reconstruct_rng if count2 is greater than zero! This is one reason to preserve occasional copies of the complete RNG state, as recorded in the RNG state file. If you have a state file, then restart_rng(filename) will always give rapid results. If the RNG state file is internally inconsistent, restart_rng will return 0, otherwise it returns 1.
Just before exiting a program that uses mrandom, a call to save_rng(filename) will preserve the final state of the RNG on disk. Note: I have found it helpful to make a save_rng call only upon normal exit from my experimental codes. In case of an error exit, it is convenient to leave the RNG state file in its initial condition. This makes it easy to retry the experiment after fixing the bug.
A demonstration routine, named mrtest.c, is included with this software distribution to help get you started with the mrandom package.
As far as I know, it is a subject of current research to decide if the pseudorandom sequence of mrandom() is superior to that of a high-precision multiplicative generator such as drand48(). A low-precision multiplicative generator, such as rand(3C), will cause problems in many applications, since non-random behavior is noticeable in the least-significant twenty bits of its output.
Currently, the best theoretical guarantees for pseudorandomness come from the theory of universal hash functions. The idea is to use a high-precision multiplicative generator with random coefficients. Thus one might consider using the mrandom package to generate random coefficients, modulo large primes, for the drand48 pseudorandom number generator.
By examination of the object code for random(), I deduce that it uses the following algorithm in its default (31-word table) configuration.
long random()
{
static int j=4, k=1;
long r;
rngstate[j] += rngstate[k];
r = (rngstate[j]>>1) & 0x7fffffff;
j++;
if (j>31) j=1;
k++;
if (k>31) k=1;
return(r);
}
The initial values for rngstate are obtained from a linear congruential generator. Any defects of this scheme will be inherited by mrandom.