Random.mesa
Copyright Ó 1985, 1986, 1991 by Xerox Corporation. All rights reserved.
MBrown on August 27, 1982 10:59 am
Russ Atkinson (RRA) February 5, 1985 2:14:40 pm PST
Random: CEDAR DEFINITIONS = BEGIN
RandomStream: TYPE = REF RandomStreamRep;
RandomStreamRep: TYPE = RECORD [
seed: INT ¬ 0,
data: REF ¬ NIL];
Create: PROC [range: INT ¬ 0, seed: INT ¬ 0] RETURNS [rs: RandomStream];
The parameters range and seed determine the sequence generated by procedure NextInt (also ChooseInt) below. If range<=0, NextInt will produce results in [0..LAST[INT]]; otherwise, NextInt will produce results in [0..range). If seed=0, a default seed value is used to determine the starting point of the sequence; if seed>0, seed is scaled if necessary and then used; if seed<0, a seed value is derived from the system clock. In any case, the seed value actually used (after scaling) is in rs.seed. Using the same seed will allow reproducible pseudo-random sequences.
Avoid small values of the range parameter; the intent of range is only to allow the same sequence to be produced by different machines.
NextInt: PROC [rs: RandomStream ¬ NIL] RETURNS [INT];
A call to NextInt returns the next term in the stream. It will be in the range dictated by the corresponding Create operation. If rs = NIL, then the default stream will be used.
ChooseInt: PROC [rs: RandomStream ¬ NIL, min: INT ¬ 0, max: INT] RETURNS [INT];
! Error [badInterval] ([min..max] is an illegal interval).
Chooses a point in the interval [min..max] at random. If rs = NIL, then the default stream will be used. (The choice is quite random, even if this interval is large.) If the interval is empty (min > max), or if the interval length (max-min+1) exceeds the range of numbers the generator was initialized to produce, raises ERROR BadInterval.
BadInterval: ERROR;
END.
Random number generators
Basic information
A generator is created by a call to Create. The stream retruned is internally monitored, so multiple processes can safely call for another random number. Concurrent calls are unlikely to lead to repeatable sequences of random numbers, however.
Sample program
The following is the skeleton of a program that uses the Random package. The program fills an array called "rolls" with random numbers that might represent die trials:
DIRECTORY
Random USING[Choose, Create],
...;
Sample: PROGRAM IMPORTS Random, ...
rolls: ARRAY [0..100) OF INT [1 .. 6];
rs: RandomStream ← Random.Create[]; -- use default seed and full range
FOR i: INT IN [0..100) DO
rolls[i] ← Random.Choose[rs: rs, min: 1, max: 6];
ENDLOOP;
...
END.
Technical details
These generators are based on an AlgolW program distributed by Donald Knuth to his CS144b class in 1975. They use the additive random number generation algorithm that is recommended in the second edition of Seminumerical Algorithms by Knuth, and that was the subject of a Ph.D. thesis by John Reiser of Stanford ("The analysis of additive random number generators", STAN-CS-77-601, March 1977.) The additive generator has several advantages over a standard linear congruential generator (lcg):
The sequences that it generates are more "random" in several ways. With an lcg generating a sequence a(n), the related sequence a(n) mod 2 has period 2, a(n) mod 4 has period 4, and so on; thus care must be taken not to derive any results primarily from the least-significant bits of a(n). An additive generator produces numbers whose bits are more uniformly random. An lcg for a short wordlength has a short period (for example, a sequence of 16 bit cardinals must cycle after 64k terms); an additive generator may have a very long period even for short wordlengths. Many lcgs (including IBM's notorious RANDU) generate sequences that are very poorly distributed in two and three dimensions (you might see this by plotting consecutive pairs or triples of terms in euclidean space and noting the patterns); additive generators do not have this problem.
The generator relatively easy to transport from machine to machine, and can be made to generate the same sequences on each machine. This can be difficult with lcgs because the sequences they generate usually depend on the way a machine handles overflows (in particular, on the wordlength.) An additive generator can produce a random sequence without ever causing an overflow.
The generator is relatively fast because it does not use multiplication, which is a time-consuming operation on many machines.
Change Log
Created by MBrown on July 2, 1979
Changed by MBrown on May 2, 1980 11:18 PM
Renamed module to conform to Cedar standards. Added defaulting of parameters to InitRandom, and named its result trueSeed.
Changed by MBrown on September 25, 1980 9:26 AM
Added Choose.
Changed by MBrown on March 9, 1982 10:47 am
Added Error, ErrorType (used to raise unnamed ERROR).
Changed by MBrown on June 8, 1982 11:04 am
Changed module name from RandomLongInt, procs Next from Random, Init from InitRandom, made module CEDAR
Changed by MBrown on August 27, 1982 11:10 am
Merged in documentation.
Russ Atkinson (RRA) January 14, 1985 5:38:18 pm PST
Rewrote this interface to make it stream oriented instead of module instance oriented.