-- File: RandomCardImpl.Mesa
-- Last edited by:

-- MBrown on August 27, 1982 3:18 pm
-- Taft, June 9, 1983 3:48 pm
-- Paul Rovner, August 9, 1983 5:27 pm

DIRECTORY
Basics USING[LowHalf],
RandomCard USING[ErrorType],
PrincOpsUtils USING[GetClockPulses];

RandomCardImpl: CEDAR MONITOR
IMPORTS
Basics, PrincOpsUtils
EXPORTS
RandomCard
= {
-- Module to produce a random sequence of cardinals.

Error: PUBLIC ERROR [ec: RandomCard.ErrorType] = CODE;


-- Constant definitions (meanings described in InitRandom below)

defaultSeed: CARDINAL = 27183;
numCalls: INTEGER = 3;


-- Module state

a: ARRAY [0..55] OF CARDINAL;
-- Holds 55 random cardinals, to be returned by Random. (A[0] is wasted to make the
--code generator produce better array accesses.)
p: INTEGER [0..55];
-- a[1..p-1] has not yet been returned by Random; p is [1..55] except within Random.


-- Procedures

Init: PUBLIC ENTRY PROC [seed: INTEGER] RETURNS [INTEGER] = {
-- The parameter seed determines the sequence generated by procedure Next below.
-- 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 integer value returned.

minSeed: CARDINAL = LAST[CARDINAL]/10;
g, gPrev, gSave: CARDINAL;

PickSeed: INTERNAL PROC RETURNS [INTEGER] = TRUSTED INLINE {
-- Returns a "random" seed in [0..LAST[INTEGER]].
RETURN[ABS[LOOPHOLE[Basics.LowHalf[LOOPHOLE[PrincOpsUtils.GetClockPulses[]]],INTEGER]]];
};--PickSeed

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;
-- Seed can't be too big since LAST[INTEGER] < LAST[CARDINAL]*(9/10)

-- The array a is initialized by placing seed in a[55], and scattering the values

-- (-1)**(i-1) * (F(i) - seed*F(i-1)) MOD maxRand, 0<i<55,

-- (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.

a[55] ← gPrev ← seed;
g ← 1;
FOR i: INTEGER IN [1..54] DO
p ← (21*i) MOD 55;
a[p] ← gSave ← g; g ← gPrev-g; gPrev ← gSave;
ENDLOOP;
THROUGH [1..numCalls) DO
RandomGen[];
ENDLOOP;
-- Show a as being empty; first call to Random will call RandomGen again.
p ← 1;
RETURN[seed]
};--InitRandom


Next: PUBLIC ENTRY PROC [] RETURNS[CARDINAL] = {
p ← p-1;
IF p=0 THEN { RandomGen[]; p ← 55 };
RETURN[a[p]] };


RandomGen: INTERNAL PROC [] = {
-- 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.)
FOR i: INTEGER IN [1..24] DO
a[i] ← a[i] - a[i+31];
ENDLOOP;
FOR i: INTEGER IN [25..55] DO
a[i] ← a[i] - a[i-24];
ENDLOOP };


Choose: PUBLIC--EXTERNAL--PROC[min, max: CARDINAL]
RETURNS[CARDINAL--[min..max]--] = {
Next: ENTRY PROC [] RETURNS[CARDINAL] = INLINE {
-- INLINE copy of public Random above.
p ← p-1;
IF p=0 THEN { RandomGen[]; p ← 55 };
RETURN[a[p]] };
intervalLen: CARDINAL;
IF min > max THEN ERROR Error [badInterval];
intervalLen ← max - min + 1; --is 0 when min=0, max=LAST[CARDINAL]
DO
-- Draw a number in [0..LAST[CARDINAL]]. 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 2^16). 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.
r, rem: CARDINAL;
r ← Next[];
IF intervalLen = 0 THEN RETURN[r];
rem ← r MOD intervalLen;
IF (r - rem) > LOOPHOLE[-LOOPHOLE[intervalLen,INTEGER],CARDINAL] THEN LOOP;
RETURN[min + rem];
ENDLOOP };

[] ← Init [seed: 0];

}.--RandomCardImpl

CHANGE LOG

Created by MBrown on June 26, 1979

Changed by MBrown on May 3, 1980 12:50 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. Made
--InitRandom return an INTEGER, so that runs are truly repeatable.

Changed by MBrown on August 24, 1980 10:44 PM
-- Made some minor changes to improve the code generated for this module by the Mesa
--compiler. Array a is now 0-origin. Array index p is now referenced more times in the
--code than a (a redundant p𡤁 is used), making it global 0. PickSeed and RandomGen are
--now INLINE (each is "called" once). The former calls to RandomGen from InitRandom are
--simulated by setting p𡤁 and then calling Random.
-- Results: 134 instructions (was 158), 176 bytes (was 206). Typical path through
--Random (p#0) is 11 instructions (was 14), 13 bytes (was 19). A clever code generator
--could still replace one LG0 with a PUSH in the typical path.
-- One observation: since INLINE expansion may decrease locality and actually slow down
--a program on a machine with a cache (Dorado), it might be useful to have control over
--whether inline expansion really happens inline, or is handled by branching to and from
--the code. This would be unnecessary if an intelligent optimizer performed code-motion
--based on user hints (e.g. what percentage of the time does a test succeed).

Changed by MBrown on September 24, 1980 10:29 PM
-- Added Choose on suggestion of Jim Mitchell (but using my algorithm). Undid the business of
--making RandomGen INLINE, to allow Random to be expanded inline in Choose.

Changed by MBrown on December 6, 1980 9:36 PM
-- Conversion to Pilot. Use GetClockPulses to generate random seed.

Changed by MBrown on March 9, 1982 11:23 am
-- Converted into a module monitor.

Changed by MBrown on June 8, 1982 11:27 am
-- Changed proc names Next from Random, Init from InitRandom, made module CEDAR.

Changed by MBrown on August 27, 1982 3:19 pm
-- Call Init[0] on start trap.

Changed by Taft on June 9, 1983 3:47 pm
-- Convert for Nucleus.