A.5.2 Random Number Generation
1
[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.
2
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.
3
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.]
3.a
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
4
The library package
Numerics.Float_Random has the following declaration:
5
package Ada.Numerics.Float_Random
is
6
-- Basic facilities
7
type Generator
is limited private;
8
subtype Uniformly_Distributed
is Float
range 0.0 .. 1.0;
function Random (Gen : Generator)
return Uniformly_Distributed;
9
procedure Reset (Gen :
in Generator;
Initiator :
in Integer);
procedure Reset (Gen :
in Generator);
10
-- Advanced facilities
11
12
procedure Save (Gen :
in Generator;
To_State :
out State);
procedure Reset (Gen :
in Generator;
From_State :
in State);
13
Max_Image_Width :
constant :=
implementation-defined integer value;
14
function Image (Of_State : State)
return String;
function Value (Coded_State : String)
return State;
15
private
... -- not specified by the language
end Ada.Numerics.Float_Random;
15.1/2
16
The generic library package Numerics.Discrete_Random
has the following declaration:
17
generic
type Result_Subtype
is (<>);
package Ada.Numerics.Discrete_Random
is
18
-- Basic facilities
19
type Generator
is limited private;
20
function Random (Gen : Generator)
return Result_Subtype;
21
procedure Reset (Gen :
in Generator;
Initiator :
in Integer);
procedure Reset (Gen :
in Generator);
22
-- Advanced facilities
23
24
procedure Save (Gen :
in Generator;
To_State :
out State);
procedure Reset (Gen :
in Generator;
From_State :
in State);
25
Max_Image_Width :
constant :=
implementation-defined integer value;
26
function Image (Of_State : State)
return String;
function Value (Coded_State : String)
return State;
27
private
... -- not specified by the language
end Ada.Numerics.Discrete_Random;
27.a
Implementation defined: The value of
Numerics.Float_Random.Max_Image_Width.
27.b
Implementation defined: The value of
Numerics.Discrete_Random.Max_Image_Width.
27.c/1
Implementation
Note: {
8652/0097} {
AI95-00115-01}
The following is a possible implementation of the private part of
Numerics.Float_Random each
package (assuming the presence of “
with Ada.Finalization;”
as a context clause):
27.d
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);
27.d.1/2
{
8652/0097}
{
AI95-00115-01}
{
AI95-00344-01}
Unfortunately,
Numerics.Discrete_Random.Generator
also can cannot be implemented this way,
as Numerics.Discrete_Random can be instantiated at any nesting depth.
However, Generator could have a component of a controlled type, as long
as that type is declared in some other (non-generic) package. One possible
solution would be to implement Numerics.Discrete_Random in terms of Numerics.Float_Random,
using a component of Numerics.Float_Random.Generator to implement Numerics.Float_Random.Generator.27.e
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.
27.1/2
{
AI95-00360-01}
The type Generator needs finalization
(see 7.6) in every instantiation of Numerics.Discrete_Random.28
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.
28.a
Discussion: The repeatability provided
by the implicit initialization may be exploited for testing or debugging
purposes.
29
An object of the private type State can be used to
hold the internal state of a generator. Such objects are only needed
if the application is designed to save and restore generator states or
to examine or manufacture them.
30
The operations on generators
affect the state and therefore the future values of the associated sequence.
The semantics of the operations on generators and states are defined
below.
31
function Random (Gen : Generator) return Uniformly_Distributed;
function Random (Gen : Generator) return Result_Subtype;
32
Obtains the “next”
random number from the given generator, relative to its current state,
according to an implementation-defined algorithm. The result of the function
in Numerics.Float_Random is delivered as a value of the subtype Uniformly_Distributed,
which is a subtype of the predefined type Float having a range of 0.0
.. 1.0. The result of the function in an instantiation of Numerics.Discrete_Random
is delivered as a value of the generic formal subtype Result_Subtype.
32.a/2
This paragraph
was deleted.Implementation defined:
The algorithms for random number generation.
32.a.1/2
Discussion: The
algorithm is the subject of a Documentation Requirement, so we don't
separately summarize this implementation-defined item.
32.b
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.
33
procedure Reset (Gen : in Generator;
Initiator : in Integer);
procedure Reset (Gen : in Generator);
34
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.
34.a
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.
35
procedure Save (Gen : in Generator;
To_State : out State);
procedure Reset (Gen : in Generator;
From_State : in State);
36
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.
37
function Image (Of_State : State) return String;
function Value (Coded_State : String) return State;
38
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.
38.a
Implementation defined: The string representation
of a random number generator's state.
Dynamic Semantics
39
Instantiation
of Numerics.Discrete_Random with a subtype having a null range raises
Constraint_Error.
40/1
This paragraph was
deleted.{
8652/0050}
{
AI95-00089}
Invoking
Value with a string that is not the image of any generator state raises
Constraint_Error.
Bounded (Run-Time) Errors
40.1/1
{
8652/0050}
{
AI95-00089}
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 might not be random in character.
That is, the sequence of values might not fulfill the implementation
requirements of this subclause. Implementation Requirements
41
A sufficiently long sequence of random numbers obtained
by successive calls to Random is approximately uniformly distributed
over the range of the result subtype.
42
The Random function in an instantiation of Numerics.Discrete_Random
is guaranteed to yield each value in its result subtype in a finite number
of calls, provided that the number of such values does not exceed 2 15.
43
Other performance requirements for the random number
generator, which apply only in implementations conforming to the Numerics
Annex, and then only in the “strict” mode defined there (see
G.2), are given in
G.2.5.
Documentation Requirements
44
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.
44.a/2
Documentation Requirement:
The algorithm used for random number
generation, including a description of its period.
45
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.
45.a/2
This paragraph
was deleted.Implementation defined:
The minimum time interval between calls
to the time-dependent Reset procedure that are guaranteed to initiate
different random number sequences.
45.b/2
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
46
Any storage associated with an object of type Generator
should be reclaimed on exit from the scope of the object.
46.a.1/2
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.
46.a
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.
47
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.
47.a/2
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.
48
18 If two or more tasks are to share the
same generator, then the tasks have to synchronize their access to the
generator as for any shared variable (see
9.10).
49
19 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.
50
20 A given implementation of the Random
function in Numerics.Float_Random may or may not be capable of delivering
the values 0.0 or 1.0. Portable applications should 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 fixed
range is needed, the application should use the Random function in an
appropriate instantiation of Numerics.Discrete_Random, rather than transforming
the result of the Random function in Numerics.Float_Random. However,
some applications with unusual requirements, such as for a sequence of
random integers each drawn from a different range, will find it more
convenient to transform the result of the floating point Random function.
For M ≥ 1, the expression
51
Integer(Float(M) * Random(G)) mod M
52
transforms the result of Random(G) to an integer uniformly
distributed over the range 0 .. M–1;
it is valid even if Random delivers 0.0 or 1.0. Each value of the result
range is possible, provided that M is not too large. Exponentially distributed
(floating point) random numbers with mean and standard deviation 1.0
can be obtained by the transformation
53/2
54
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
55
Example of a program
that plays a simulated dice game:
56
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;
57
Example of a program
that simulates coin tosses:
58
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;
59
Example of a parallel
simulation of a physical system, with a separate generator of event probabilities
in each task:
60
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;
61
21 Notes on the last example: 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
61.a/2
{
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
61.b/2
{
8652/0050}
{
AI95-00089-01}
Corrigendum: Made the passing of an incorrect
Image of a generator a bounded error, as it may not be practical to check
for problems (if a generator consists of several related values).
Ada 2005 and 2012 Editions sponsored in part by Ada-Europe
