1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
"http://www.w3.org/TR/html4/loose.dtd">
<HTML>
<HEAD>
<TITLE>AARM95 - Performance Requirements for Random Number Generation</TITLE>
<META NAME="Author" CONTENT="JTC1/SC22/WG9/ARG, by Randall Brukardt, ARG Editor">
<META NAME="GENERATOR" CONTENT="Arm_Form.Exe, Ada Reference Manual generator">
<STYLE type="text/css">
DIV.paranum {position: absolute; font-family: Arial, Helvetica, sans-serif; left: 0.5 em; top: auto}
TT {font-family: "Courier New", monospace}
DT {display: compact}
DIV.Normal {font-family: "Times New Roman", Times, serif; margin-bottom: 0.6em}
DIV.Wide {font-family: "Times New Roman", Times, serif; margin-top: 0.6em; margin-bottom: 0.6em}
DIV.Annotations {font-family: "Times New Roman", Times, serif; margin-left: 4.0em; margin-bottom: 0.6em}
DIV.WideAnnotations {font-family: "Times New Roman", Times, serif; margin-left: 4.0em; margin-top: 0.6em; margin-bottom: 0.6em}
DIV.Index {font-family: "Times New Roman", Times, serif}
DIV.SyntaxSummary {font-family: "Times New Roman", Times, serif; margin-left: 2.0em; margin-bottom: 0.4em}
DIV.Notes {font-family: "Times New Roman", Times, serif; margin-left: 2.0em; margin-bottom: 0.6em}
DIV.NotesHeader {font-family: "Times New Roman", Times, serif; margin-left: 2.0em}
DIV.SyntaxIndented {font-family: "Times New Roman", Times, serif; margin-left: 2.0em; margin-bottom: 0.4em}
DIV.Indented {font-family: "Times New Roman", Times, serif; margin-left: 6.0em; margin-bottom: 0.6em}
DIV.CodeIndented {font-family: "Times New Roman", Times, serif; margin-left: 4.0em; margin-bottom: 0.6em}
DIV.SmallIndented {font-family: "Times New Roman", Times, serif; margin-left: 10.0em; margin-bottom: 0.6em}
DIV.SmallCodeIndented {font-family: "Times New Roman", Times, serif; margin-left: 8.0em; margin-bottom: 0.6em}
DIV.Examples {font-family: "Courier New", monospace; margin-left: 2.0em; margin-bottom: 0.6em}
DIV.SmallExamples {font-family: "Courier New", monospace; font-size: 80%; margin-left: 7.5em; margin-bottom: 0.6em}
DIV.IndentedExamples {font-family: "Courier New", monospace; margin-left: 8.0em; margin-bottom: 0.6em}
DIV.SmallIndentedExamples {font-family: "Courier New", monospace; font-size: 80%; margin-left: 15.0em; margin-bottom: 0.6em}
UL.Bulleted {font-family: "Times New Roman", Times, serif; margin-left: 2.0em; margin-right: 2.0em; margin-top: 0em; margin-bottom: 0.5em}
UL.SmallBulleted {font-family: "Times New Roman", Times, serif; margin-left: 6.0em; margin-right: 6.0em; margin-top: 0em; margin-bottom: 0.5em}
UL.NestedBulleted {font-family: "Times New Roman", Times, serif; margin-left: 4.0em; margin-right: 4.0em; margin-top: 0em; margin-bottom: 0.5em}
UL.SmallNestedBulleted {font-family: "Times New Roman", Times, serif; margin-left: 8.0em; margin-right: 8.0em; margin-top: 0em; margin-bottom: 0.5em}
UL.IndentedBulleted {font-family: "Times New Roman", Times, serif; margin-left: 8.0em; margin-right: 8.0em; margin-top: 0em; margin-bottom: 0.5em}
UL.CodeIndentedBulleted {font-family: "Times New Roman", Times, serif; margin-left: 6.0em; margin-right: 6.0em; margin-top: 0em; margin-bottom: 0.5em}
UL.CodeIndentedNestedBulleted {font-family: "Times New Roman", Times, serif; margin-left: 8.0em; margin-right: 8.0em; margin-top: 0em; margin-bottom: 0.5em}
UL.SyntaxIndentedBulleted {font-family: "Times New Roman", Times, serif; margin-left: 4.0em; margin-right: 4.0em; margin-top: 0em; margin-bottom: 0.5em}
UL.NotesBulleted {font-family: "Times New Roman", Times, serif; margin-left: 4.0em; margin-right: 4.0em; margin-top: 0em; margin-bottom: 0.5em}
UL.NotesNestedBulleted {font-family: "Times New Roman", Times, serif; margin-left: 6.0em; margin-right: 6.0em; margin-top: 0em; margin-bottom: 0.5em}
DL.Hanging {font-family: "Times New Roman", Times, serif; margin-top: 0em; margin-bottom: 0.6em}
DD.Hanging {margin-left: 6.0em}
DL.IndentedHanging {font-family: "Times New Roman", Times, serif; margin-left: 4.0em; margin-top: 0em; margin-bottom: 0.6em}
DD.IndentedHanging {margin-left: 2.0em}
DL.HangingInBulleted {font-family: "Times New Roman", Times, serif; margin-left: 2.0em; margin-right: 2.0em; margin-top: 0em; margin-bottom: 0.5em}
DD.HangingInBulleted {margin-left: 4.0em}
DL.SmallHanging {font-family: "Times New Roman", Times, serif; margin-left: 4.0em; margin-top: 0em; margin-bottom: 0.6em}
DD.SmallHanging {margin-left: 7.5em}
DL.SmallIndentedHanging {font-family: "Times New Roman", Times, serif; margin-left: 8.0em; margin-top: 0em; margin-bottom: 0.6em}
DD.SmallIndentedHanging {margin-left: 2.0em}
DL.SmallHangingInBulleted {font-family: "Times New Roman", Times, serif; margin-left: 6.0em; margin-right: 6.0em; margin-top: 0em; margin-bottom: 0.5em}
DD.SmallHangingInBulleted {margin-left: 5.0em}
DL.Enumerated {font-family: "Times New Roman", Times, serif; margin-right: 0.0em; margin-top: 0em; margin-bottom: 0.5em}
DD.Enumerated {margin-left: 2.0em}
DL.SmallEnumerated {font-family: "Times New Roman", Times, serif; margin-left: 4.0em; margin-right: 4.0em; margin-top: 0em; margin-bottom: 0.5em}
DD.SmallEnumerated {margin-left: 2.5em}
DL.NestedEnumerated {font-family: "Times New Roman", Times, serif; margin-left: 2.0em; margin-right: 2.0em; margin-top: 0em; margin-bottom: 0.5em}
DL.SmallNestedEnumerated {font-family: "Times New Roman", Times, serif; margin-left: 6.0em; margin-right: 6.0em; margin-top: 0em; margin-bottom: 0.5em}
</STYLE>
</HEAD>
<BODY TEXT="#000000" BGCOLOR="#FFFFF0" LINK="#0000FF" VLINK="#800080" ALINK="#FF0000">
<P><A HREF="AA-TOC.html">Contents</A> <A HREF="AA-0-29.html">Index</A> <A HREF="AA-G-2-4.html">Previous</A> <A HREF="AA-G-2-6.html">Next</A></P>
<HR>
<H1> G.2.5 Performance Requirements for Random Number Generation</H1>
<DIV Class="Paranum"><FONT SIZE=-2>1</FONT></DIV>
<DIV Class="Normal"> In the strict mode, the performance of Numerics.Float_Random
and Numerics.Discrete_Random shall be as specified here. </DIV>
<H4 ALIGN=CENTER>Implementation Requirements</H4>
<DIV Class="Paranum"><FONT SIZE=-2>2</FONT></DIV>
<DIV Class="Normal"> 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.</DIV>
<DIV Class="Paranum"><FONT SIZE=-2>3</FONT></DIV>
<DIV Class="Normal"> The implementation's representations of generator
states and its algorithms for generating random numbers shall yield a
period of at least 2<SUP><FONT SIZE=+1><FONT SIZE=-2>31</FONT></FONT></SUP>-2;
much longer periods are desirable but not required.</DIV>
<DIV Class="Paranum"><FONT SIZE=-2>4</FONT></DIV>
<DIV Class="Normal"> 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. </DIV>
<DIV Class="Paranum"><FONT SIZE=-2>4.a</FONT></DIV>
<DIV Class="Annotations"><FONT SIZE=-1><B>Implementation Note: </B>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, <I>The Art of Computer
Programming, vol. 2: Seminumerical Algorithms.</I> 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.
</FONT></DIV>
<DIV Class="Paranum"><FONT SIZE=-2>4.b</FONT></DIV>
<UL Class="SmallBulleted"><FONT SIZE=-1><LI TYPE=DISC>Proportional Distribution Test (a variant of the Equidistribution
Test). The interval 0.0 .. 1.0 is partitioned into <I>K</I> subintervals.
<I>K</I> 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 <I>K</I>-1.</LI></FONT></UL>
<DIV Class="Paranum"><FONT SIZE=-2>4.c</FONT></DIV>
<UL Class="SmallBulleted"><FONT SIZE=-1><LI TYPE=DISC>Gap Test. The bounds of a range <I>A</I> .. <I>B</I>, with
0.0 <= <I>A</I> < <I>B</I> <= 1.0, are chosen randomly for each repetition
of the test, subject to the constraint that 0.2 <= <I>B</I>-<I>A</I>
<= 0.6. Random floating point numbers are generated until 5000 falling
into the range <I>A</I> .. <I>B</I> 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 <I>A</I> ..
<I>B</I>. 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 <I>P</I> = <I>B</I>-<I>A</I>. The probability
that a gap has a length of <I>L</I> is (1-<I>P</I>) <SUP><FONT SIZE=+1><FONT SIZE=-2><I>L</I></FONT></FONT></SUP>
· <I>P</I> for <I>L</I> <= 15, while the probability that a gap
has a length of 16 or more is (1-<I>P</I>) <SUP><FONT SIZE=+1><FONT SIZE=-2>16</FONT></FONT></SUP>.
The number of degrees of freedom for the chi-square test is 16.</LI></FONT></UL>
<DIV Class="Paranum"><FONT SIZE=-2>4.d</FONT></DIV>
<UL Class="SmallBulleted"><FONT SIZE=-1><LI TYPE=DISC>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.</LI></FONT></UL>
<DIV Class="Paranum"><FONT SIZE=-2>4.e</FONT></DIV>
<UL Class="SmallBulleted"><FONT SIZE=-1><LI TYPE=DISC>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 <I>L</I> is 1/<I>L</I>!
- 1/(<I>L</I>+1)! for <I>L</I> <= 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.</LI></FONT></UL>
<DIV Class="Paranum"><FONT SIZE=-2>4.f</FONT></DIV>
<UL Class="SmallBulleted"><FONT SIZE=-1><LI TYPE=DISC>Decreasing-Runs Test. The test is similar to the Increasing
Runs Test, but with decreasing runs.</LI></FONT></UL>
<DIV Class="Paranum"><FONT SIZE=-2>4.g</FONT></DIV>
<UL Class="SmallBulleted"><FONT SIZE=-1><LI TYPE=DISC>Maximum-of-<I>t</I> Test (with <I>t</I> = 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. </LI></FONT></UL>
<DIV Class="Paranum"><FONT SIZE=-2>4.h</FONT></DIV>
<DIV Class="Annotations"><FONT SIZE=-1><B>Implementation Note: </B>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 (<I>op. cit.</I>) 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. </FONT></DIV>
<DIV Class="Paranum"><FONT SIZE=-2>4.i</FONT></DIV>
<UL Class="SmallBulleted"><FONT SIZE=-1><LI TYPE=DISC>Equidistribution Test. In each repetition of the test,
a number <I>R</I> between 2 and 30 is chosen randomly, and Numerics.Discrete_Random
is instantiated with an integer subtype whose range is 1 .. <I>R</I>.
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 <I>R</I>-1.</LI></FONT></UL>
<DIV Class="Paranum"><FONT SIZE=-2>4.j</FONT></DIV>
<UL Class="SmallBulleted"><FONT SIZE=-1><LI TYPE=DISC>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 <I>K</I> different
denominations (1 <= <I>K</I> <= 5) are tallied and compared with the
expected counts. The probability that a hand contains exactly <I>K</I>
different denominations is given by a formula in Knuth. The number of
degrees of freedom for the chi-square test is 4.</LI></FONT></UL>
<DIV Class="Paranum"><FONT SIZE=-2>4.k</FONT></DIV>
<UL Class="SmallBulleted"><FONT SIZE=-1><LI TYPE=DISC>Coupon Collector's Test. Numerics.Discrete_Random is instantiated
in each repetition of the test with an integer subtype whose range is
1 .. <I>R</I>, where <I>R</I> varies systematically from 2 to 11. Integers
are generated randomly from this range until each value in the range
has occurred, and the number <I>K</I> of integers generated is recorded.
This constitutes a ``coupon collector's segment'' of length <I>K</I>.
2000 such segments are generated. The counts of segments of each length
from <I>R</I> to <I>R</I>+29, and of all lengths greater than <I>R</I>+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.</LI></FONT></UL>
<DIV Class="Paranum"><FONT SIZE=-2>4.l</FONT></DIV>
<UL Class="SmallBulleted"><FONT SIZE=-1><LI TYPE=DISC>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
<I>point</I>, 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 <= <I>S</I> <= 12, let <I>D</I>
<SUB><FONT SIZE=+1><FONT SIZE=-2><I>S</I></FONT></FONT></SUB> be the
probability that a roll of a pair of dice shows the sum <I>S</I>, and
let <I>Q</I> <SUB><FONT SIZE=+1><FONT SIZE=-2><I>S</I></FONT></FONT></SUB>(<I>L</I>)
= <I>D</I> <SUB><FONT SIZE=+1><FONT SIZE=-2><I>S</I></FONT></FONT></SUB>
· (1 - (<I>D</I> <SUB><FONT SIZE=+1><FONT SIZE=-2><I>S</I></FONT></FONT></SUB>
+ <I>D</I> <SUB><FONT SIZE=+1><FONT SIZE=-2>7</FONT></FONT></SUB>))
<SUP><FONT SIZE=+1><FONT SIZE=-2><I>L</I>-2</FONT></FONT></SUP> ·
(<I>D</I> <SUB><FONT SIZE=+1><FONT SIZE=-2><I>S</I></FONT></FONT></SUB>
+ <I>D</I> <SUB><FONT SIZE=+1><FONT SIZE=-2>7</FONT></FONT></SUB>).
Then, the probability that a game has a length of 1 is <I>D</I> <SUB><FONT SIZE=+1><FONT SIZE=-2>7</FONT></FONT></SUB>
+ <I>D</I> <SUB><FONT SIZE=+1><FONT SIZE=-2>11</FONT></FONT></SUB>
+ <I>D</I> <SUB><FONT SIZE=+1><FONT SIZE=-2>2</FONT></FONT></SUB>
+ <I>D</I> <SUB><FONT SIZE=+1><FONT SIZE=-2>3</FONT></FONT></SUB>
+ <I>D</I> <SUB><FONT SIZE=+1><FONT SIZE=-2>12</FONT></FONT></SUB>
and, for <I>L</I> > 1, the probability that a game has a length of
<I>L</I> is <I>Q</I> <SUB><FONT SIZE=+1><FONT SIZE=-2>4</FONT></FONT></SUB>(<I>L</I>)
+ <I>Q</I> <SUB><FONT SIZE=+1><FONT SIZE=-2>5</FONT></FONT></SUB>(<I>L</I>)
+ <I>Q</I> <SUB><FONT SIZE=+1><FONT SIZE=-2>6</FONT></FONT></SUB>(<I>L</I>)
+ <I>Q</I> <SUB><FONT SIZE=+1><FONT SIZE=-2>8</FONT></FONT></SUB>(<I>L</I>)
+ <I>Q</I> <SUB><FONT SIZE=+1><FONT SIZE=-2>9</FONT></FONT></SUB>(<I>L</I>)
+ <I>Q</I> <SUB><FONT SIZE=+1><FONT SIZE=-2>10</FONT></FONT></SUB>(<I>L</I>).
The number of degrees of freedom for the chi-square test is 18.</LI></FONT></UL>
<DIV Class="Paranum"><FONT SIZE=-2>4.m</FONT></DIV>
<UL Class="SmallBulleted"><FONT SIZE=-1><LI TYPE=DISC>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 <I>pass</I>, 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 <I>L</I>
>= 0, the probability that a pass has a length of <I>L</I> is <I>W</I>
<SUP><FONT SIZE=+1><FONT SIZE=-2><I>L</I></FONT></FONT></SUP> ·
(1-<I>W</I>), where <I>W</I>, 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.</LI></FONT></UL>
<DIV Class="Paranum"><FONT SIZE=-2>4.n</FONT></DIV>
<UL Class="SmallBulleted"><FONT SIZE=-1><LI TYPE=DISC>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. </LI></FONT></UL>
<HR>
<P><A HREF="AA-TOC.html">Contents</A> <A HREF="AA-0-29.html">Index</A> <A HREF="AA-G-2-4.html">Previous</A> <A HREF="AA-G-2-6.html">Next</A> <A HREF="AA-TTL.html">Legal</A></P>
</BODY>
</HTML>
|
