<<>> <> <> <> <> <> <> <> <> <> DIRECTORY Random USING [RandomStream, RandomStreamRep]; RandomImpl: CEDAR MONITOR LOCKS pd USING pd: PrivateData EXPORTS Random = { OPEN 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] = { <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; <> WHILE seedmaxSeed DO seed ¬ seed/3 ENDLOOP; rs.seed ¬ seed; <> }; { <> <<(-1)**(i-1) * (F(i) - seed*F(i-1)) MOD pd.maxRand, 0> <<(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 LOOPHOLE[g, CARD] ¬ LOOPHOLE[g, CARD] + 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 LOOPHOLE[g, CARD] ¬ LOOPHOLE[g, CARD] + maxRand; pd.a[i] ¬ g; ENDLOOP; FOR i: -- HighIndex -- [0..HighLimit] IN HighIndex DO -- because compiler bias bug g: INT ¬ pd.a[i] - pd.a[i-LowLimit]; IF g<0 THEN LOOPHOLE[g, CARD] ¬ LOOPHOLE[g, CARD] + 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] = { <> RETURN[ABS[LOOPHOLE[TicksForSeed[], INT]]]; }; TicksForSeed: PROC RETURNS [CARD] = TRUSTED MACHINE CODE { "XR_TicksSinceBoot" }; 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 <> <> <> <<>> <<>> <<>> <<>> <<>>