RandomImpl.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
MBrown on August 27, 1982 3:09 pm
Taft on June 9, 1983 3:49 pm
Russ Atkinson (RRA) February 5, 1985 2:53:23 pm PST
DIRECTORY
Basics USING [CARD],
Random USING [RandomStream, RandomStreamRep],
PrincOpsUtils USING [GetClockPulses];
RandomImpl:
CEDAR
MONITOR
LOCKS pd USING pd: PrivateData
IMPORTS PrincOpsUtils
EXPORTS Random = { OPEN Basics, Random;
BadInterval: PUBLIC ERROR = CODE;
Constant definitions
defaultSeed:
INT = 1354117939;
Described in InitRandom below.
numCalls:
INTEGER = 3;
Described in InitRandom below.
Module state
PrivateData: TYPE = REF PrivateDataRep;
PrivateDataRep:
TYPE =
MONITORED RECORD [
a:
ARRAY Index
OF
INT,
Holds 55 random long integers, to be returned by Random. (A[0] is wasted to make the code generator produce better array accesses.)
p: Index,
a[1..p-1] has not yet been returned by Random; p is [1..55] except within Random.
maxRand:
CARD
Largest integer produced by the generator + 1.
];
Index:
TYPE =
CARDINAL [0..HighLimit];
LowIndex: TYPE = CARDINAL [1..LowLimit];
HighIndex: TYPE = CARDINAL (LowLimit..HighLimit];
HighLimit: CARDINAL = 55;
LowLimit: CARDINAL = 24;
Create:
PUBLIC
PROC [range, seed:
INT]
RETURNS [rs: RandomStream] = {
The parameters range and seed determine the sequence generated by procedure NextInt (and ChooseInt) below. If range<=0, Next will produce results in [0..LAST[INT]]; otherwise, Next 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 the INT value returned by Init. Avoid small values of the range parameter; the intent of range is to allow the same sequence to be produced different machines.
pd: PrivateData ← NEW[PrivateDataRep];
rs ← NEW[RandomStreamRep ← [seed: seed, data: pd]];
{
minSeed: INT;
maxSeed: INT;
IF range <= 0
THEN pd.maxRand ← LOOPHOLE[range ← LAST[INT], CARD] + 1
ELSE pd.maxRand ← range;
minSeed ← range/10;
maxSeed ← range - minSeed;
IF seed<0 THEN seed ← PickSeed[];
IF seed=0 THEN seed ← defaultSeed;
Now scale the seed into the proper range (no log routine available...)
WHILE seed<minSeed DO seed ← seed*3 ENDLOOP;
WHILE seed>maxSeed DO seed ← seed/3 ENDLOOP;
rs.seed ← seed;
Save this in case the user wants to reproduce this series.
};
{
The array a is initialized by placing seed in a[HighLimit], and scattering the values
(-1)**(i-1) * (F(i) - seed*F(i-1)) MOD pd.maxRand, 0<i<HighLimit,
(where F(i) denotes the i-th Fibonacci number) throughout the rest of a. Then the generating procedure RandomGen is called, numCalls times, to make things sufficiently random.
g: INT ← 1;
gPrev: INT ← pd.a[HighLimit] ← seed;
FOR i:
CARDINAL
IN [1..HighLimit)
DO
p: Index ← (21*i) MOD HighLimit;
gSave: INT ← pd.a[p] ← g;
g ← gPrev-g;
gPrev ← gSave;
IF g<0 THEN g ← g + pd.maxRand;
ENDLOOP;
THROUGH [1..numCalls)
DO
RandomGen[pd];
ENDLOOP;
Show pd.a as being empty; first call to NextIntEntry will call RandomGen again.
pd.p ← 1;
};
};
NextInt:
PUBLIC
PROC [rs: RandomStream]
RETURNS [
INT] = {
Get the next INT in the stream.
IF rs = NIL THEN rs ← defaultStream;
WITH rs.data
SELECT
FROM
pd: PrivateData => RETURN [NextIntEntry[pd]];
ENDCASE => ERROR;
};
NextIntEntry:
ENTRY
PROC [pd: PrivateData]
RETURNS [
INT] = {
Note that we assume that p # 0 on entry. We obviously maintain this on exit. p = 1 after Create, so we should be OK.
p: Index ← pd.p - 1;
IF p=0 THEN { RandomGen[pd]; p ← HighLimit };
RETURN[pd.a[pd.p ← p]];
};
RandomGen:
PROC [pd: PrivateData] = {
Additive random number generator using the recurrence y(n) = y(n-55) - y(n-24) mod maxRand. See John F. Reiser, "Analysis of Additive Random Number Generators", STAN-CS-77-601, March 1977, or Knuth Volume 2 (second edition.)
maxRand: CARD ← pd.maxRand;
FOR i: LowIndex
IN LowIndex
DO
g: INT ← pd.a[i] - pd.a[i+(HighLimit-LowLimit)];
IF g<0 THEN g ← g + maxRand;
pd.a[i] ← g;
ENDLOOP;
FOR i: HighIndex
IN HighIndex
DO
g: INT ← pd.a[i] - pd.a[i-LowLimit];
IF g<0 THEN g ← g + maxRand;
pd.a[i] ← g;
ENDLOOP;
};
ChooseInt:
PUBLIC
PROC [rs: RandomStream, min, max:
INT]
RETURNS [
INT
--[min..max]--] = {
intervalLen: CARD;
IF min > max THEN ERROR BadInterval;
intervalLen ← LOOPHOLE[max - min, CARD] + 1;
IF rs = NIL THEN rs ← defaultStream;
WITH rs.data
SELECT
FROM
pd: PrivateData => {
IF (intervalLen <= 0) OR (intervalLen > pd.maxRand) THEN ERROR BadInterval;
DO
Draw a number in [0..pd.maxRand).
r: CARD ← NextIntEntry[pd];
rem: CARD ← r;
IF rem >= intervalLen
THEN {
We want to reject this number if it lies in the "odd interval" at the high end of this range (there is no odd interval if intervalLen divides maxRand). The funny test below does it (claim). The average number of numbers drawn is less than 2, and much closer to 1 for small intervalLen.
rem ← r MOD intervalLen;
IF (r - rem) > (pd.maxRand-intervalLen) THEN LOOP;
};
RETURN[min + rem];
ENDLOOP;
};
ENDCASE => ERROR;
};
PickSeed:
PROC []
RETURNS [
INT] =
TRUSTED {
Returns a "random" seed in [0..LAST[INT]].
RETURN[ABS[LOOPHOLE[PrincOpsUtils.GetClockPulses[],INT]]];
};
defaultStream: RandomStream ← Create[range: 0, seed: 0];
CHANGE LOG
Created by MBrown on July 2, 1979
Changed by MBrown on May 2, 1980 11:07 PM
Renamed module to conform to Cedar standards. Commented-out all subrange
declarations on local integer variables, since subranges that don't start at 0 produce
bad code. Fixed bug in InitRandom that caused it to loop if PickSeed returned 0.
Changed by MBrown on September 25, 1980 9:41 AM
Added Choose; made minor changes to improve code generated. See RandomCardImpl for details.
Changed by MBrown on December 6, 1980 9:59 PM
Conversion to Pilot. Use GetClockPulses to generate random seed.
Changed by MBrown on March 9, 1982 10:37 am
Converted into a module monitor. Added Error to interface.
Changed by MBrown on June 8, 1982 10:59 am
Changed module name from RandomLongIntImpl, Next from Random, Init from InitRandom,
made implementation CEDAR (with one TRUSTED call to System.GetClockPulses).
Changed by MBrown on August 27, 1982 3:09 pm
Call Init [0, 0] on start trap.
Changed by Taft on June 9, 1983 3:48 pm
Convert for Nucleus.
Russ Atkinson (RRA) January 14, 1985 6:08:01 pm PST
Rewrote this program to make it stream oriented instead of module instance oriented.
, }