-- File: RandomIntImpl.Mesa
-- Last edited by:
-- MBrown on August 27, 1982 3:18 pm
-- Paul Rovner on June 9, 1982 8:03 am
-- Taft on June 9, 1983 3:50 pm
DIRECTORY
Basics USING[LowHalf],
RandomInt USING[ErrorType],
PrincOpsUtils USING[GetClockPulses];
RandomIntImpl: CEDAR MONITOR
IMPORTS
Basics, PrincOpsUtils
EXPORTS
RandomInt
= {
-- Module to produce a random sequence of integers.
Error: PUBLIC ERROR [ec: RandomInt.ErrorType] = CODE;
-- Constant definitions
defaultSeed: INTEGER = 13541;
-- Described in Init below.
numCalls: INTEGER = 3;
-- Described in Init below.
-- Module state
a: ARRAY [0..55] OF INTEGER;
-- Holds 55 random integers, 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.
maxRand: CARDINAL;
-- Largest integer produced by the generator + 1.
-- Procedures
Init: PUBLIC ENTRY PROC [range, seed: INTEGER] RETURNS [INTEGER] = {
-- The parameters range and seed determine the sequence generated by procedure
--Next below.
-- If range<=0, Next will produce results in [0..LAST[INTEGER]]; 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 integer
--value returned by Init.
minSeed,maxSeed: INTEGER;
g, gPrev, gSave: INTEGER;
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 range<=0 THEN {
maxRand ← LOOPHOLE[LAST[INTEGER],CARDINAL] + 1;
minSeed ← LAST[INTEGER]/10;
maxSeed ← LAST[INTEGER] - minSeed }
ELSE {
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;
-- 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: CARDINAL IN [1..54] DO
p ← (21*i) MOD 55;
a[p] ← gSave ← g; g ← gPrev-g; gPrev ← gSave;
IF g<0 THEN g ← g + maxRand;
ENDLOOP;
THROUGH [1..numCalls) DO
RandomGen[];
ENDLOOP;
-- Show a as being empty; first call to Random will call RandomGen again.
p ← 1;
RETURN[seed]
};--Init
Next: PUBLIC ENTRY PROC [] RETURNS [INTEGER] = {
-- A call to Next returns the next term in the sequence determined by the most
--recent call to Init.
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.)
g: INTEGER;
FOR i: INTEGER IN [1..24] DO
g ← a[i] - a[i+31];
IF g<0 THEN g ← g + maxRand;
a[i] ← g
ENDLOOP;
FOR i: INTEGER IN [25..55] DO
g ← a[i] - a[i-24];
IF g<0 THEN g ← g + maxRand;
a[i] ← g
ENDLOOP };
Choose: PUBLIC--EXTERNAL--PROC [min, max: INTEGER]
RETURNS [INTEGER--[min..max]--] = {
Next: ENTRY PROC [] RETURNS [INTEGER] = INLINE {
-- INLINE copy of public Next 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=FIRST[INTEGER], max=LAST[INTEGER]
IF (intervalLen = 0) OR (intervalLen > maxRand) THEN ERROR Error [badInterval];
DO
-- Draw a number in [0..maxRand). 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.
r, rem: CARDINAL;
rem ← (r ← Next[]) MOD intervalLen;
IF (r - rem) > (maxRand - intervalLen) THEN LOOP;
RETURN[min + rem];
ENDLOOP };
[] ← Init [range: 0, seed: 0];
}.--RandomIntImpl
CHANGE LOG
Created by MBrown on July 2, 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.
Changed by MBrown on September 24, 1980 11:25 PM
-- Added Choose; made minor changes to improve code generated. See RandomCardImpl for details.
Changed by MBrown on December 6, 1980 9:57 PM
-- Conversion to Pilot. Use GetClockPulses to generate random seed.
Changed by MBrown on March 9, 1982 10:24 am
-- Converted into a module monitor.
Changed by MBrown on June 8, 1982 11:34 am
-- Changed proc names Next from Random, Init from InitRandom,
--made implementation CEDAR (with one TRUSTED call to System.GetClockPulses).
-- Fixed minor performance glitch in Choose.
Changed by Paul Rovner on June 9, 1982 8:03 am
-- Changed name Init from InitRandom (Mark forgot to do so).
Changed by MBrown on August 27, 1982 3:17 pm
-- Call Init [0, 0] on start trap.
Changed by Taft on June 9, 1983 3:50 pm
-- Convert for Nucleus.