Random Number Generation

[Facilities for the generation of pseudo-random floating point numbers are provided in the package Numerics.Float_Random; the generic package Numerics.Discrete_Random provides similar facilities for the generation of pseudo-random integers and pseudo-random values of enumeration types. For brevity, pseudo-random values of any of these types are called random numbers.

Some of the facilities provided are basic to all applications of random numbers. These include a limited private type each of whose objects serves as the generator of a (possibly distinct) sequence of random numbers; a function to obtain the “next” random number from a given sequence of random numbers (that is, from its generator); and subprograms to initialize or reinitialize a given generator to a time-dependent state or a state denoted by a single integer.

Other facilities are provided specifically for advanced applications. These include subprograms to save and restore the state of a given generator; a private type whose objects can be used to hold the saved state of a generator; and subprograms to obtain a string representation of a given generator state, or, given such a string representation, the corresponding state.]

Discussion: These facilities support a variety of requirements ranging from repeatable sequences (for debugging) to unique sequences in each execution of a program.

Static Semantics

{AI12-0302-1}    procedure Reset (Gen       : in Generator;
                    Initiator : in Integer)
      with Global => overriding in out Gen;
   procedure Reset (Gen       : in Generator)
      with Global => overriding in out Gen;

{AI12-0302-1}    procedure Save  (Gen        : in  Generator;
                    To_State   : out State);
   procedure Reset (Gen        : in  Generator;
                    From_State : in  State)
      with Global => overriding in out Gen;

{AI12-0144-1} {AI12-0302-1}    function Random (Gen   : Generator;
                    First : Result_Subtype;
                    Last  : Result_Subtype) return Result_Subtype
      with Post => Random'Result in First .. Last,
           Global => overriding in out Gen;

Implementation defined: The value of Numerics.Float_Random.Max_Image_Width.

Implementation defined: The value of Numerics.Discrete_Random.Max_Image_Width.

Implementation Note: {8652/0097} {AI95-00115-01} The following is a possible implementation of the private part of Numerics.Float_Random (assuming the presence of “with Ada.Finalization;” as a context clause):

type State is ...;
type Access_State is access State;
type Generator is new Finalization.Limited_Controlled with
   record
      S : Access_State := new State'(...);
   end record;
procedure Finalize (G : in out Generator);

{8652/0097} {AI95-00115-01} {AI95-00344-01} Numerics.Discrete_Random.Generator also can be implemented this way.

Clearly some level of indirection is required in the implementation of a Generator, since the parameter mode is in for all operations on a Generator. For this reason, Numerics.Float_Random and Numerics.Discrete_Random cannot be declared pure.

An object of the limited private type Generator is associated with a sequence of random numbers. Each generator has a hidden (internal) state, which the operations on generators use to determine the position in the associated sequence. All generators are implicitly initialized to an unspecified state that does not vary from one program execution to another; they may also be explicitly initialized, or reinitialized, to a time-dependent state, to a previously saved state, or to a state uniquely denoted by an integer value.

Discussion: The repeatability provided by the implicit initialization may be exploited for testing or debugging purposes.

{AI05-0280-1} {AI12-0445-1} An object of the private type State can be used to hold the internal state of a generator. Such objects are only necessary if the application is designed to save and restore generator states or to examine or manufacture them. The implicit initial value of type State corresponds to the implicit initial value of all generators.

Discussion: {AI05-0280-1} All generators are implicitly initialized to the same unchanging value, and using Reset on a default initialized object of type State will produce a generator with that same value.

This paragraph was deleted.

Discussion: The algorithm is the subject of a Documentation Requirement, so we don't separately summarize this implementation-defined item.

Reason: The requirement for a level of indirection in accessing the internal state of a generator arises from the desire to make Random a function, rather than a procedure.

{AI12-0144-1} Obtains the “next” random number from the given generator, relative to its current state, according to an implementation-defined algorithm. If the range First .. Last is a null range, Constraint_Error is raised.

Sets the state of the specified generator to one that is an unspecified function of the value of the parameter Initiator (or to a time-dependent state, if only a generator parameter is specified). The latter form of the procedure is known as the time-dependent Reset procedure.

Implementation Note: The time-dependent Reset procedure can be implemented by mapping the current time and date as determined by the system clock into a state, but other implementations are possible. For example, a white-noise generator or a radioactive source can be used to generate time-dependent states.

Save obtains the current state of a generator. Reset gives a generator the specified state. A generator that is reset to a state previously obtained by invoking Save is restored to the state it had when Save was invoked.

Image provides a representation of a state coded (in an implementation-defined way) as a string whose length is bounded by the value of Max_Image_Width. Value is the inverse of Image: Value(Image(S)) = S for each state S that can be obtained from a generator by invoking Save.

Implementation defined: The string representation of a random number generator's state.

Dynamic Semantics

Bounded (Run-Time) Errors

{8652/0050} {AI95-00089} {AI12-0445-1} It is a bounded error to invoke Value with a string that is not the image of any generator state. If the error is detected, Constraint_Error or Program_Error is raised. Otherwise, a call to Reset with the resulting state will produce a generator such that calls to Random with this generator will produce a sequence of values of the appropriate subtype, but which are not necessarily random in character. That is, the sequence of values do not necessarily fulfill the implementation requirements of this subclause.

Implementation Requirements

{AI12-0144-1} Each call of a Random function has a result range; this is the range First .. Last for the version of Random with First and Last parameters and the range of the result subtype of the function otherwise.

Discussion: {AI12-0005-1} {AI12-0144-1} In this rule, “consecutive” means at least that there are no intervening explicit calls involving the same generator. This restricts the rule to only applying to cases where just the Random function changes the generator. We don't mean to impose a requirement if there are intervening calls to Reset, to Random with the same generator but a different result range, or any other case that would affect the sequence of values returned. Operations that use the resulting random values (for instance, to store them somewhere) are not considered in determining if calls are consecutive.

{AI12-0144-1} A Random function in an instantiation of Numerics.Discrete_Random is guaranteed to yield each value in its result range in a finite number of calls, provided that the number of such values does not exceed 2¹⁵.

Documentation Requirements

No one algorithm for random number generation is best for all applications. To enable the user to determine the suitability of the random number generators for the intended application, the implementation shall describe the algorithm used and shall give its period, if known exactly, or a lower bound on the period, if the exact period is unknown. Periods that are so long that the periodicity is unobservable in practice can be described in such terms, without giving a numerical bound.

Documentation Requirement: The algorithm used for random number generation, including a description of its period.

The implementation also shall document the minimum time interval between calls to the time-dependent Reset procedure that are guaranteed to initiate different sequences, and it shall document the nature of the strings that Value will accept without raising Constraint_Error.

This paragraph was deleted.

Documentation Requirement: The minimum time interval between calls to the time-dependent Reset procedure that is guaranteed to initiate different random number sequences.

Implementation Advice

Implementation Advice: Any storage associated with an object of type Generator of the random number packages should be reclaimed on exit from the scope of the object.

Ramification: A level of indirection is implicit in the semantics of the operations, given that they all take parameters of mode in. This implies that the full type of Generator probably should be a controlled type, with appropriate finalization to reclaim any heap-allocated storage.

If the generator period is sufficiently long in relation to the number of distinct initiator values, then each possible value of Initiator passed to Reset should initiate a sequence of random numbers that does not, in a practical sense, overlap the sequence initiated by any other value. If this is not possible, then the mapping between initiator values and generator states should be a rapidly varying function of the initiator value.

Implementation Advice: Each value of Initiator passed to Reset for the random number packages should initiate a distinct sequence of random numbers, or, if that is not possible, be at least a rapidly varying function of the initiator value.

NOTE 2 Within a given implementation, a repeatable random number sequence can be obtained by relying on the implicit initialization of generators or by explicitly initializing a generator with a repeatable initiator value. Different sequences of random numbers can be obtained from a given generator in different program executions by explicitly initializing the generator to a time-dependent state.

NOTE 3 {AI12-0442-1} {AI12-0447-1} A given implementation of the Random function in Numerics.Float_Random is not guaranteed to be capable of delivering the values 0.0 or 1.0. Applications will be more portable if they assume that these values, or values sufficiently close to them to behave indistinguishably from them, can occur. If a sequence of random integers from some range is necessary, the application should use one of the Random functions in an appropriate instantiation of Numerics.Discrete_Random, rather than transforming the result of the Random function in Numerics.Float_Random.

Reason: {AI12-0442-1} One might think that a simple transformation of the result of the floating point Random function such as Integer(Float(M) * Random(G)) mod M would give a uniform distribution. But this is only true if the period of the underlying generator is a multiple of M. (This usually requires that M be a power of two.) In other cases, the mod operation maps slightly more random values to some result values than others. It is easy to see this: consider a 4-bit random integer (with a range of 0 .. 15). If one mods this by 6 to get a value in 0 .. 5 (to which one would add 1 to get the value of a die roll), 3 values would be mapped to each value 0 .. 3, but only 2 values would be mapped to 4 and 5. Even when the input is uniformly distributed, the output clearly is not. A similar effect occurs regardless of the number of bits in the random integer. Since it takes care to get this right, users should use the provided functions (which presumably do this correctly – AI12-0144-1 contains a correct algorithm) and resist the urge to “roll-their-own”.

where Log comes from Numerics.Elementary_Functions (see A.5.1); in this expression, the addition of Float'Model_Small avoids the exception that would be raised were Log to be given the value zero, without affecting the result (in most implementations) when Random returns a nonzero value.

Examples

with Ada.Numerics.Discrete_Random;
procedure Dice_Game is
   subtype Die is Integer range 1 .. 6;
   subtype Dice is Integer range 2*Die'First .. 2*Die'Last;
   package Random_Die is new Ada.Numerics.Discrete_Random (Die);
   use Random_Die;
   G : Generator;
   D : Dice;
begin
   Reset (G);  -- Start the generator in a unique state in each run
   loop
      -- Roll a pair of dice; sum and process the results
      D := Random(G) + Random(G);
      ...
   end loop;
end Dice_Game;

with Ada.Numerics.Discrete_Random;
procedure Flip_A_Coin is
   type Coin is (Heads, Tails);
   package Random_Coin is new Ada.Numerics.Discrete_Random (Coin);
   use Random_Coin;
   G : Generator;
begin
   Reset (G);  -- Start the generator in a unique state in each run
   loop
      -- Toss a coin and process the result
      case Random(G) is
          when Heads =>
             ...
          when Tails =>
             ...
      end case;
   ...
   end loop;
end Flip_A_Coin;

with Ada.Numerics.Float_Random;
procedure Parallel_Simulation is
   use Ada.Numerics.Float_Random;
   task type Worker is
      entry Initialize_Generator (Initiator : in Integer);
      ...
   end Worker;
   W : array (1 .. 10) of Worker;
   task body Worker is
      G : Generator;
      Probability_Of_Event : Uniformly_Distributed;
   begin
      accept Initialize_Generator (Initiator : in Integer) do
         Reset (G, Initiator);
      end Initialize_Generator;
      loop
         ...
         Probability_Of_Event := Random(G);
         ...
      end loop;
   end Worker;
begin
   -- Initialize the generators in the Worker tasks to different states
   for I in W'Range loop
      W(I).Initialize_Generator (I);
   end loop;
   ... -- Wait for the Worker tasks to terminate
end Parallel_Simulation;

{AI12-0452-1} Although each Worker task initializes its generator to a different state, those states will be the same in every execution of the program. The generator states can be initialized uniquely in each program execution by instantiating Ada.Numerics.Discrete_Random for the type Integer in the main procedure, resetting the generator obtained from that instance to a time-dependent state, and then using random integers obtained from that generator to initialize the generators in each Worker task.

Incompatibilities With Ada 95

{AI95-00360-01} Amendment Correction: Type Generator in Numerics.Float_Random and in an instance of Numerics.Discrete_Random is defined to need finalization. If the restriction No_Nested_Finalization (see D.7) applies to the partition, and Generator does not have a controlled part, it will not be allowed in local objects in Ada 2005 whereas it would be allowed in original Ada 95. Such code is not portable, as another Ada compiler may have a controlled part in Generator, and thus would be illegal.

Wording Changes from Ada 95

{8652/0050} {AI95-00089-01} {AI05-0005-1} Corrigendum: Made the passing of an incorrect Image of a generator a bounded error, as it might not be practical to check for problems (if a generator consists of several related values).

Wording Changes from Ada 2005

{AI05-0280-1} Correction: Specified the implicit initial value for (sub)type State. This was unspecified in Ada 95 and Ada 2005, so a program depending on some other initial value is very unlikely and certainly was not portable. An implementation can use default expressions, aspect Default_Value, or aspect Default_Component_Value to keep the representation of the type unchanged while meeting this new requirement.

A.5.2 Random Number Generation