Contents Index Search Previous Next

1

In the strict mode, the performance of Numerics.Float_Random
and Numerics.Discrete_Random shall be as specified here.

2

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.

3

The implementation's representations of generator
states and its algorithms for generating random numbers shall yield a
period of at least 2^{31}-2;
much longer periods are desirable but not required.

4

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.

4.a

4.b

- 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.

4.c

- 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.

4.d

- 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.

4.e

- 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.

4.f

- Decreasing-Runs Test. The test is similar to the Increasing Runs Test, but with decreasing runs.

4.g

- 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.

4.h

4.i

- 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.

4.j

- 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.

4.k

- 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.

4.l

- 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.

4.m

- 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.

4.n

- 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.