[Cyan]<Cedar6.0>BasicPackages>RandomImpl.mesa!3

RandomImpl.mesa

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;

Procedures

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;

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.

, }