G.2.5 Performance Requirements for Random Number Generation
In the strict mode, the performance of Numerics.Float_Random
and Numerics.Discrete_Random shall be as specified here.
Implementation Requirements
Two different calls to the time-dependent Reset procedure
shall reset the generator to different states, provided that the calls
are separated in time by at least one second and not more than fifty
years.
The implementation's representations of generator
states and its algorithms for generating random numbers shall yield a
period of at least 231–2;
much longer periods are desirable but not required.
The implementations of Numerics.Float_Random.Random
and Numerics.Discrete_Random.Random shall pass at least 85% of the individual
trials in a suite of statistical tests. For Numerics.Float_Random, the
tests are applied directly to the floating point values generated (i.e.,
they are not converted to integers first), while for Numerics.Discrete_Random
they are applied to the generated values of various discrete types. Each
test suite performs 6 different tests, with each test repeated 10 times,
yielding a total of 60 individual trials. An individual trial is deemed
to pass if the chi-square value (or other statistic) calculated for the
observed counts or distribution falls within the range of values corresponding
to the 2.5 and 97.5 percentage points for the relevant degrees of freedom
(i.e., it shall be neither too high nor too low). For the purpose of
determining the degrees of freedom, measurement categories are combined
whenever the expected counts are fewer than 5.
Implementation Note: In the floating
point random number test suite, the generator is reset to a time-dependent
state at the beginning of the run. The test suite incorporates the following
tests, adapted from D. E. Knuth, The Art of Computer Programming,
vol. 2: Seminumerical Algorithms. In the descriptions below, the
given number of degrees of freedom is the number before reduction due
to any necessary combination of measurement categories with small expected
counts; it is one less than the number of measurement categories.
Proportional Distribution Test (a variant
of the Equidistribution Test). The interval 0.0 .. 1.0 is partitioned
into K subintervals. K
is chosen randomly between 4 and 25 for each repetition of the test,
along with the boundaries of the subintervals (subject to the constraint
that at least 2 of the subintervals have a width of 0.001 or more). 5000
random floating point numbers are generated. The counts of random numbers
falling into each subinterval are tallied and compared with the expected
counts, which are proportional to the widths of the subintervals. The
number of degrees of freedom for the chi-square test is K–1.
Gap Test. The bounds of a range A
.. B, with 0.0 ≤ A
< B ≤ 1.0, are chosen randomly
for each repetition of the test, subject to the constraint that 0.2 ≤
B–A
≤ 0.6. Random floating point numbers are generated until 5000 falling
into the range A .. B
have been encountered. Each of these 5000 is preceded by a “gap”
(of length greater than or equal to 0) of consecutive random numbers
not falling into the range A .. B.
The counts of gaps of each length from 0 to 15, and of all lengths greater
than 15 lumped together, are tallied and compared with the expected counts.
Let P = B–A.
The probability that a gap has a length of L
is (1–P) L
· P for L
≤ 15, while the probability that a gap has a length of 16 or more
is (1–P) 16.
The number of degrees of freedom for the chi-square test is 16.
Permutation Test. 5000 tuples of 4 different
random floating point numbers are generated. (An entire 4-tuple is discarded
in the unlikely event that it contains any two exactly equal components.)
The counts of each of the 4! = 24 possible relative orderings of the
components of the 4-tuples are tallied and compared with the expected
counts. Each of the possible relative orderings has an equal probability.
The number of degrees of freedom for the chi-square test is 23.
Increasing-Runs Test. Random floating point
numbers are generated until 5000 increasing runs have been observed.
An “increasing run” is a sequence of random numbers in strictly
increasing order; it is followed by a random number that is strictly
smaller than the preceding random number. (A run under construction is
entirely discarded in the unlikely event that one random number is followed
immediately by an exactly equal random number.) The decreasing random
number that follows an increasing run is discarded and not included with
the next increasing run. The counts of increasing runs of each length
from 1 to 4, and of all lengths greater than 4 lumped together, are tallied
and compared with the expected counts. The probability that an increasing
run has a length of L is 1/L!
– 1/(L+1)! for L
≤ 4, while the probability that an increasing run has a length of
5 or more is 1/5!. The number of degrees of freedom for the chi-square
test is 4.
Decreasing-Runs Test. The test is similar
to the Increasing Runs Test, but with decreasing runs.
Maximum-of-t
Test (with t = 5). 5000 tuples of 5
random floating point numbers are generated. The maximum of the components
of each 5-tuple is determined and raised to the 5th power. The uniformity
of the resulting values over the range 0.0 .. 1.0 is tested as in the
Proportional Distribution Test.
Implementation Note: In the discrete
random number test suite, Numerics.Discrete_Random is instantiated as
described below. The generator is reset to a time-dependent state after
each instantiation. The test suite incorporates the following tests,
adapted from D. E. Knuth (op. cit.) and other sources. The given
number of degrees of freedom for the chi-square test is reduced by any
necessary combination of measurement categories with small expected counts,
as described above.
Equidistribution Test. In each repetition
of the test, a number R between 2 and
30 is chosen randomly, and Numerics.Discrete_Random is instantiated with
an integer subtype whose range is 1 .. R.
5000 integers are generated randomly from this range. The counts of occurrences
of each integer in the range are tallied and compared with the expected
counts, which have equal probabilities. The number of degrees of freedom
for the chi-square test is R–1.
Simplified Poker Test. Numerics.Discrete_Random
is instantiated once with an enumeration subtype representing the 13
denominations (Two through Ten, Jack, Queen, King, and Ace) of an infinite
deck of playing cards. 2000 “poker” hands (5-tuples of values
of this subtype) are generated randomly. The counts of hands containing
exactly K different denominations (1
≤ K ≤ 5) are tallied and compared
with the expected counts. The probability that a hand contains exactly
K different denominations is given
by a formula in Knuth. The number of degrees of freedom for the chi-square
test is 4.
Coupon Collector's Test. Numerics.Discrete_Random
is instantiated in each repetition of the test with an integer subtype
whose range is 1 .. R, where R
varies systematically from 2 to 11. Integers are generated randomly from
this range until each value in the range has occurred, and the number
K of integers generated is recorded.
This constitutes a “coupon collector's segment” of length
K. 2000 such segments are generated.
The counts of segments of each length from R
to R+29, and of all lengths greater
than R+29 lumped together, are tallied
and compared with the expected counts. The probability that a segment
has any given length is given by formulas in Knuth. The number of degrees
of freedom for the chi-square test is 30.
Craps Test (Lengths of Games). Numerics.Discrete_Random
is instantiated once with an integer subtype whose range is 1 .. 6 (representing
the six numbers on a die). 5000 craps games are played, and their lengths
are recorded. (The length of a craps game is the number of rolls of the
pair of dice required to produce a win or a loss. A game is won on the
first roll if the dice show 7 or 11; it is lost if they show 2, 3, or
12. If the dice show some other sum on the first roll, it is called the
point, and the game is won if and only if the point is rolled
again before a 7 is rolled.) The counts of games of each length from
1 to 18, and of all lengths greater than 18 lumped together, are tallied
and compared with the expected counts. For 2 ≤ S
≤ 12, let D S
be the probability that a roll of a pair of dice shows the sum S,
and let Q S(L)
= D S
· (1 – (D S
+ D 7))
L–2
· (D S
+ D 7).
Then, the probability that a game has a length of 1 is D
7
+ D 11
+ D 2
+ D 3
+ D 12
and, for L > 1, the probability
that a game has a length of L is Q
4(L)
+ Q 5(L)
+ Q 6(L)
+ Q 8(L)
+ Q 9(L)
+ Q 10(L).
The number of degrees of freedom for the chi-square test is 18.
Craps Test (Lengths of Passes). This test
is similar to the last, but enough craps games are played for 3000 losses
to occur. A string of wins followed by a loss is called a pass,
and its length is the number of wins preceding the loss. The counts of
passes of each length from 0 to 7, and of all lengths greater than 7
lumped together, are tallied and compared with the expected counts. For
L ≥ 0, the probability that a pass
has a length of L is W
L
· (1–W), where W,
the probability that a game ends in a win, is 244.0/495.0. The number
of degrees of freedom for the chi-square test is 8.
Collision Test. Numerics.Discrete_Random is
instantiated once with an integer or enumeration type representing binary
bits. 15 successive calls on the Random function are used to obtain the
bits of a 15-bit binary integer between 0 and 32767. 3000 such integers
are generated, and the number of collisions (integers previously generated)
is counted and compared with the expected count. A chi-square test is
not used to assess the number of collisions; rather, the limits on the
number of collisions, corresponding to the 2.5 and 97.5 percentage points,
are (from formulas in Knuth) 112 and 154. The test passes if and only
if the number of collisions is in this range.
Sponsored by Ada-Europe