-- File: RandomImpl.mesa
-- Last edited by:
--   MBrown on August 27, 1982 3:09 pm
--   Taft on June 9, 1983 3:49 pm

  DIRECTORY
    Random USING [ErrorType],
    PrincOpsUtils USING [GetClockPulses];

RandomImpl: CEDAR MONITOR
  IMPORTS
    PrincOpsUtils
  EXPORTS
    Random
  = {
  -- Module to produce a random sequence of long integers.

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


  -- Constant definitions

  defaultSeed: INT = 1354117939;
    -- Described in InitRandom below.
  numCalls: INTEGER = 3;
    -- Described in InitRandom below.


-- Module state
  
  a: ARRAY [0..55] 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: INTEGER [0..55];
    -- a[1..p-1] has not yet been returned by Random; p is [1..55] except within Random.
  maxRand: LONG CARDINAL;  
    -- Largest integer produced by the generator + 1.


  -- Procedures

  Init: PUBLIC ENTRY PROC [range, seed: INT] RETURNS [INT] = {
    -- The parameters range and seed determine the sequence generated by procedure
    --Next (and Choose) 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.

    minSeed,maxSeed: INT;
    g, gPrev, gSave: INT;

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

    IF range<=0 THEN {
      maxRand _ LOOPHOLE[LAST[INT],LONG CARDINAL] + 1;
      minSeed _ LAST[INT]/10;
      maxSeed _ LAST[INT] - 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 [INT] = {
    -- 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: INT;
    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: INT] RETURNS [INT--[min..max]--] = {
    Next: ENTRY PROC [] RETURNS [INT] = INLINE {
      -- INLINE copy of public Next above.
      p _ p-1;
      IF p=0 THEN {  RandomGen[];  p _ 55  };
      RETURN[a[p]] };
    intervalLen: LONG CARDINAL;
    IF min > max THEN ERROR Error[badInterval];
    intervalLen _ max - min + 1; --is 0 when min=FIRST[INT], max=LAST[INT]
    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: LONG CARDINAL;
      rem _ (r _ Next[]) MOD intervalLen;
      IF (r - rem) > (maxRand-intervalLen) THEN LOOP;
      RETURN[min + rem];
      ENDLOOP };

  [] _ Init [range: 0, seed: 0];

  }.--RandomImpl


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.