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; defaultSeed: INT = 1354117939; numCalls: INTEGER = 3; PrivateData: TYPE = REF PrivateDataRep; PrivateDataRep: TYPE = MONITORED RECORD [ a: ARRAY Index OF INT, p: Index, maxRand: CARD ]; 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] = { 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; WHILE seedmaxSeed DO seed _ seed/3 ENDLOOP; rs.seed _ seed; }; { 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; pd.p _ 1; }; }; NextInt: PUBLIC PROC [rs: RandomStream] RETURNS [INT] = { 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] = { p: Index _ pd.p - 1; IF p=0 THEN { RandomGen[pd]; p _ HighLimit }; RETURN[pd.a[pd.p _ p]]; }; RandomGen: PROC [pd: PrivateData] = { 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 r: CARD _ NextIntEntry[pd]; rem: CARD _ r; IF rem >= intervalLen THEN { rem _ r MOD intervalLen; IF (r - rem) > (pd.maxRand-intervalLen) THEN LOOP; }; RETURN[min + rem]; ENDLOOP; }; ENDCASE => ERROR; }; PickSeed: PROC [] RETURNS [INT] = TRUSTED { 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 Changed by MBrown on September 25, 1980 9:41 AM Changed by MBrown on December 6, 1980 9:59 PM Changed by MBrown on March 9, 1982 10:37 am Changed by MBrown on June 8, 1982 10:59 am Changed by MBrown on August 27, 1982 3:09 pm Changed by Taft on June 9, 1983 3:48 pm òRandomImpl.mesa Copyright c 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 Constant definitions Described in InitRandom below. Described in InitRandom below. Module state Holds 55 random long integers, to be returned by Random. (A[0] is wasted to make the code generator produce better array accesses.) a[1..p-1] has not yet been returned by Random; p is [1..55] except within Random. Largest integer produced by the generator + 1. Procedures 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. Now scale the seed into the proper range (no log routine available...) 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