Oberon || Library || Module Index || Search Engine || Definition || Module


Ulm's Oberon Library:
RandomGenerators


NAME

RandomGenerators - general abstraction for pseudo random number generation

SYNOPSIS

TYPE Sequence = POINTER TO SequenceRec;
TYPE SequenceRec = RECORD (Services.ObjectRec) END;
TYPE Int32ValSProc = PROCEDURE (sequence: Sequence): Types.Int32;
TYPE LongRealValSProc = PROCEDURE (sequence: Sequence): LONGREAL;
TYPE RewindSequenceProc = PROCEDURE (sequence: Sequence);
TYPE RestartSequenceProc = PROCEDURE (sequence, seed: Sequence);
TYPE SetValSProc = PROCEDURE (sequence: Sequence; value: Operations.Operand);
CONST int32ValS = 0; longRealValS = 1; rewindSequence = 2; restartSequence = 3;
TYPE CapabilitySet = SET; (* of [int32ValS..restartSequence] *)
TYPE Interface = POINTER TO InterfaceRec;
TYPE InterfaceRec =
   RECORD
      (Objects.ObjectRec)
      int32ValS: Int32ValSProc;
      longRealValS: LongRealValSProc;
      rewindSequence: RewindSequenceProc;
      restartSequence: RestartSequenceProc;
   END;


VAR std: Sequence; (* default sequence *) VAR seed: Sequence; (* sequence of seed values *) VAR unpredictable: Sequence; (* initially NIL *)

PROCEDURE Init(sequence: Sequence; if: Interface; caps: CapabilitySet); PROCEDURE Capabilities(sequence: Sequence): CapabilitySet; PROCEDURE RewindSequence(sequence : Sequence); PROCEDURE RestartSequence(sequence, seed: Sequence); PROCEDURE Int32Val(): Types.Int32; PROCEDURE Int32ValS(sequence: Sequence): Types.Int32; PROCEDURE LongRealVal(): LONGREAL; PROCEDURE LongRealValS(sequence: Sequence): LONGREAL; PROCEDURE RealVal(): REAL; PROCEDURE RealValS(sequence: Sequence): REAL; PROCEDURE Val(low, high: LONGINT): LONGINT; PROCEDURE ValS(sequence: Sequence; low, high: LONGINT): LONGINT; PROCEDURE Flip(): BOOLEAN; PROCEDURE FlipS(sequence: Sequence): BOOLEAN; PROCEDURE Support(type: Services.Type; setValS: SetValSProc); PROCEDURE SetVal(value: Operations.Operand); PROCEDURE SetValS(sequence: Sequence; value: Operations.Operand);

DESCRIPTION

RandomGenerators provides a general interface for the generation of pseudo random numbers. It also provides a linear congruential generator taken from Knuth, Seminumerical Algorithms, Third Edition, Sect. 3.6, as a default implementation.

std is a sequence predefined by the default implementation that can (and probably should) be replaced by any convenient alternative, like, e.g., a sequence from SubtractiveRandomGenerator. It serves as a default for all procedures without a sequence argument.

seed is a sequence of seed values useful to initialize other sequences. By default, it depends on the system clock at program initialization in a half-hearted effort to get something different each time a program is run. A better job will be done if a more sophisticated system-dependent true random generator like UnixSeeds is imported, which will replace this sequence.

unpredictable is, if non-NIL, to be considered as a sequence of fairly unpredictable values that is based upon good seed values and a generator like SurfRandomGenerators. The current version of UnixSeeds attempts to initialize this sequence, if imported.

Init initializes a newly created sequence and associates it with the given interface if and set of capabilities caps. At least one of int32ValS or longRealValS must be in caps and for each capability in caps a corresponding interface procedure must be defined in if. The interface procedures are expected to meet the specifications following:

int32ValS: PROCEDURE(sequence: Sequence) : Types.Int32;
return a uniformly distributed random 32 bit integer value.

longRealValS: PROCEDURE(sequence: Sequence) : LONGREAL;
return an approximately uniformly distributed random LONGREAL value in the half-open interval [0, 1). The distribution of the most significant bits will have the greatest impact on the distribution of integer values constructed from such values.

rewindSequence: PROCEDURE(sequence: Sequence);
allow to re-examine the sequence from the beginning. Only deterministic generators will implement this.

restartSequence: PROCEDURE(sequence, seed: Sequence);
restart a sequence with new seed values, supplied by seed. Only generators benefiting from seed values will implement this.

Capabilities returns the set of capabilities of sequence.

RewindSequence allows to re-examine the sequence, if supported by the implementation. It must not be called unless rewindSequence is a capability of sequence.

RestartSequence restarts a sequence with new seed values supplied by seed, if supported by the implementation. It must not be called unless restartSequence is a capability of sequence.

Int32Val returns a random 32 bit integer value, Val returns a random LONGINT value in the range from low up to high inclusively, where low must be less or equal to high, Flip returns a random boolean value, and LongRealVal and RealVal return random real values greater or equal to zero and less than one. All these functions iterate the std sequence. Their dual versions, Int32ValS, ValS, FlipS, LongRealValS, and RealValS, each iterate the sequence specified by the first parameter.

RandomGenerators defines a service for the creation of random values of a specific type. With Support, a service provider can bind an implementation of setValS to the specified type. The interface procedure is expected to meet the specification following:

setValS: PROCEDURE(sequence: Sequence; value: Operations.Operand);
store a random value obtained from sequence into value, which is supposed to be initialized already. The range of the type specified by op has to be determined by the service provider.

SetVal and SetValS store random values obtained from std or a given sequence, respectively, into value, which is supposed to be initialized already.

EXAMPLE

Following example shows how a service provider for random complex numbers may be implemented:

Suppose, a module called ComplexNumbers defines a type for complex numbers:

TYPE ComplexNumber = POINTER TO ComplexNumberRec;
TYPE ComplexNumberRec =
   RECORD
      (Operations.OperandRec)
      real: LONGREAL;
      imag: LONGREAL;
   END;
Now an implementation of the service can be realized as follows:
MODULE RandComplexNumbers;

   IMPORT ComplexNumbers, Math, RandomGenerators, Services;

   VAR
      complexType: Services.Type;

   PROCEDURE RandComplexNumber(sequence: RandomGenerators.Sequence;
                               value: Operations.Operand);
      VAR
         arg: LONGREAL;
   BEGIN
      WITH value: ComplexNumbers.ComplexNumber DO
         arg := 2. * Math.pi * RandomGenerators.LongRealValS(sequence);
         value.real := Math.CosL(arg);
         value.imag := Math.SinL(arg);
      END;
   END RandComplexNumber;

BEGIN
   Services.SeekType("ComplexNumbers.ComplexNumber", complexType);
   ASSERT(complexType # NIL);
   RandomGenerators.Support(complexType, RandComplexNumber);
END RandComplexNumbers.
Applications may now import RandComplexNumbers and generate random complex numbers with an absolute value of one by calling RandomGenerators.SetValS or RandomGenerators.SetVal.

DIAGNOSTICS

All of the following errors lead to failed assertions: Calling Init without at least one of int32ValS or longRealValS in caps or with capabilities not matched by corresponding interface procedures; calling RewindSequence or RestartSequence with a sequence lacking the corresponding capability; calling Val or ValS with a value of low greater than high.

AUTHOR

Frank B.J. Fischer, extended by Martin Hasch and Andreas Borchert

SEE ALSO

BBS
implementation of the Blum, Blum, and Shub pseudo random number generator
SubtractiveRandomGenerator
pseudo random number generator that is based on the subtractive method
SurfRandomGenerators
implementation of SURF, a simple unpredictable random function that is reasonably fast
UnixSeeds
generation of seed values in a UNIX environment

BUGS

John von Neumann (1951): Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin.
Edited by: borchert, last change: 2004/12/11, revision: 1.10, converted to HTML: 2004/12/11

Oberon || Library || Module Index || Search Engine || Definition || Module