--FILE: RandomCodeRandomImpl.mesa
--Last Edited by: Sturgis, October 9, 1984 11:15:17 am PDT


DIRECTORY
 RandomCodeRandom USING[];

RandomCodeRandomImpl: CEDAR PROGRAM EXPORTS RandomCodeRandom =

BEGIN
-- random number stuff (February 13, 1978) (by jim morris and Jim Mitchell)
-- modified to be in a record August 26, 1982 5:36 pm: Sturgis

Degree: CARDINAL = 33;
MidPower: CARDINAL = 13;
RandomState: TYPE = REF RandomStateBody;
RandomStateBody: PUBLIC TYPE = RECORD[
  table: ARRAY[0..Degree) OF CARDINAL,
  index: CARDINAL,
  trailer: CARDINAL];
  
MorrisRandomTable: ARRAY [0..Degree) OF CARDINAL ← [56572B, 112312B, 4714B, 100763B, 62510B, 1572B, 12255B, 132113B, 166574B, 2440B, 104704B, 105254B, 106030B, 7053B, 56322B, 41163B, 11105B, 136203B, 55327B, 125100B, 76206B, 167173B, 173672B, 33211B, 134253B, 153317B, 25327B, 136567B, 171517B, 23161B, 44276B, 72324B, 143455B]; -- these initial values were obtained by calling InitRandom[123].
MorrisRandomIndex: CARDINAL ← 0;
MorrisRandomTrailer: CARDINAL ← Degree-MidPower;

InitRandom: PUBLIC PROCEDURE[seed: CARDINAL] RETURNS[state: RandomState] =
BEGIN
i: CARDINAL;
xseed: CARDINAL;

 state ← NEW[RandomStateBody];
 
FOR i IN [0..Degree) DO state.table[i] ← 0 ENDLOOP;
state.table[0] ← 2*seed+1;
xseed ← seed;
FOR i IN [1..MIN[16, Degree-1]] DO
state.table[i] ← IF LOOPHOLE[xseed, INTEGER] < 0 THEN 1 ELSE 0;
xseed ← 2*xseed;
ENDLOOP;
state.index ← 0;
state.trailer ← Degree-MidPower;
THROUGH [1..2000] DO [] ← Random[state] ENDLOOP;
RETURN;
END;

Random: PUBLIC PROCEDURE [state: RandomState] RETURNS [CARDINAL] =
BEGIN
Result: CARDINAL = state.table[state.index]+state.table[state.trailer];
state.table[state.index] ← Result;
SELECT state.index+1 FROM
< Degree =>
BEGIN
state.index ← state.index+1;
state.trailer ← IF state.trailer < Degree-1 THEN state.trailer+1 ELSE 0;
END;
= Degree =>
BEGIN
state.index ← 0;
state.trailer ← Degree - MidPower;
END;
ENDCASE => ERROR; -- should never be greater than Degree
RETURN [Result];
END;

END.

MODULE HISTORY

Initial by: Sturgis, October 9, 1984 11:16:06 am PDT: edited from RandomCodeTestImpl