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
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
|
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<title>Boost Random Number Library Concepts</title>
</head>
<body bgcolor="#FFFFFF" text="#000000">
<h1>Random Number Generator Library Concepts</h1>
<h2>Introduction</h2>
Random numbers are required in a number of different problem domains,
such as
<ul>
<li>numerics (simulation, Monte-Carlo integration)
<li>games (non-deterministic enemy behavior)
<li>security (key generation)
<li>testing (random coverage in white-box tests)
</ul>
The Boost Random Number Generator Library provides a framework
for random number generators with well-defined properties so that the
generators can be used in the demanding numerics and security domains.
For a general introduction to random numbers in numerics, see
<blockquote>
"Numerical Recipes in C: The art of scientific computing", William
H. Press, Saul A. Teukolsky, William A. Vetterling, Brian P. Flannery,
2nd ed., 1992, pp. 274-328
</blockquote>
Depending on the requirements of the problem domain, different
variations of random number generators are appropriate:
<ul>
<li>non-deterministic random number generator
<li>pseudo-random number generator
<li>quasi-random number generator
</ul>
All variations have some properties in common, these concepts (in the
STL sense) are called NumberGenerator and
UniformRandomNumberGenerator. Each concept will be defined in a
subsequent section.
<p>
The goals for this library are the following:
<ul>
<li>allow easy integration of third-party random-number generators
<li>define a validation interface for the generators
<li>provide easy-to-use front-end classes which model popular
distributions
<li>provide maximum efficiency
<li>allow control on quantization effects in front-end processing
(not yet done)
</ul>
<h2><a name="number_generator">Number Generator</a></h2>
A number generator is a <em>function object</em> (std:20.3
[lib.function.objects]) that takes zero arguments. Each call to
<code>operator()</code> returns a number.
In the following table, <code>X</code> denotes a number generator
class returning objects of type <code>T</code>, and <code>u</code> is
a value of <code>X</code>.
<p>
<table border=1>
<tr><th colspan=3 align=center><code>NumberGenerator</code>
requirements</th></tr>
<tr><td>expression</td><td>return type</td>
<td>pre/post-condition</td></tr>
<tr><td><code>X::result_type</code></td><td>T</td>
<td><code>std::numeric_limits<T>::is_specialized</code> is true,
<code>T</code> is <code>LessThanComparable</code></td></tr>
<tr><td><code>u.operator()()</code></td><td>T</td><td>-</td></tr>
</table>
<p>
<em>Note:</em> The NumberGenerator requirements do not impose any
restrictions on the characteristics of the returned numbers.
<h2><a name="uniform-rng">Uniform Random Number Generator</a></h2>
A uniform random number generator is a NumberGenerator that provides a
sequence of random numbers uniformly distributed on a given range.
The range can be compile-time fixed or available (only) after run-time
construction of the object.
<p>
The <em>tight lower bound</em> of some (finite) set S is the (unique)
member l in S, so that for all v in S, l <= v holds. Likewise, the
<em>tight upper bound</em> of some (finite) set S is the (unique)
member u in S, so that for all v in S, v <= u holds.
<p>
In the following table, <code>X</code> denotes a number generator
class returning objects of type <code>T</code>, and <code>v</code> is
a const value of <code>X</code>.
<p>
<table border=1>
<tr><th colspan=3 align=center><code>UniformRandomNumberGenerator</code>
requirements</th></tr>
<tr><td>expression</td><td>return type</td>
<td>pre/post-condition</td></tr>
<tr><td><code>X::has_fixed_range</code></td><td><code>bool</code></td>
<td>compile-time constant; if <code>true</code>, the range on which
the random numbers are uniformly distributed is known at compile-time
and members <code>min_value</code> and <code>max_value</code>
exist. <em>Note:</em> This flag may also be <code>false</code> due to
compiler limitations.</td></tr>
<tr><td><code>X::min_value</code></td><td><code>T</code></td>
<td>compile-time constant; <code>min_value</code> is equal to
<code>v.min()</code></td></tr>
<tr><td><code>X::max_value</code></td><td><code>T</code></td>
<td>compile-time constant; <code>max_value</code> is equal to
<code>v.max()</code></td></tr>
<tr><td><code>v.min()</code></td><td><code>T</code></td>
<td>tight lower bound on the set of all values returned by
<code>operator()</code>. The return value of this function shall not
change during the lifetime of the object.</td></tr>
<tr><td><code>v.max()</code></td><td><code>T</code></td>
<td>if <code>std::numeric_limits<T>::is_integer</code>, tight
upper bound on the set of all values returned by
<code>operator()</code>, otherwise, the smallest representable number
larger than the tight upper bound on the set of all values returned by
<code>operator()</code>. In any case, the return value of this
function shall not change during the lifetime of the
object.</code></td></tr>
</table>
<p>
The member functions <code>min</code>, <code>max</code>, and
<code>operator()</code> shall have amortized constant time complexity.
<p>
<em>Note:</em> For integer generators (i.e. integer <code>T</code>),
the generated values <code>x</code> fulfill <code>min() <= x <=
max()</code>, for non-integer generators (i.e. non-integer
<code>T</code>), the generated values <code>x</code> fulfill
<code>min() <= x < max()</code>.
<br>
<em>Rationale:</em> The range description with <code>min</code> and
<code>max</code> serves two purposes. First, it allows scaling of the
values to some canonical range, such as [0..1). Second, it describes
the significant bits of the values, which may be relevant for further
processing.
<br>
The range is a closed interval [min,max] for integers, because the
underlying type may not be able to represent the half-open interval
[min,max+1). It is a half-open interval [min, max) for non-integers,
because this is much more practical for borderline cases of continuous
distributions.
<p>
<em>Note:</em> The UniformRandomNumberGenerator concept does not
require <code>operator()(long)</code> and thus it does not fulfill the
RandomNumberGenerator (std:25.2.11 [lib.alg.random.shuffle])
requirements. Use the
<a href="random-misc.html#random_number_generator"><code>random_number_generator</code></a>
adapter for that.
<br>
<em>Rationale:</em> <code>operator()(long)</code> is not provided,
because mapping the output of some generator with integer range to a
different integer range is not trivial.
<h2><a name="nondet-rng">Non-deterministic Uniform Random Number
Generator</a></h2>
A non-deterministic uniform random number generator is a
UniformRandomNumberGenerator that is based on some stochastic process.
Thus, it provides a sequence of truly-random numbers. Examples for
such processes are nuclear decay, noise of a Zehner diode, tunneling
of quantum particles, rolling a die, drawing from an urn, and tossing
a coin. Depending on the environment, inter-arrival times of network
packets or keyboard events may be close approximations of stochastic
processes.
<p>
The class
<code><a href="nondet_random.html#random_device">random_device</a></code>
is a model for a non-deterministic random number generator.
<p>
<em>Note:</em> This type of random-number generator is useful for
security applications, where it is important to prevent that an
outside attacker guesses the numbers and thus obtains your
encryption or authentication key. Thus, models of this concept should
be cautious not to leak any information, to the extent possible by the
environment. For example, it might be advisable to explicitly clear
any temporary storage as soon as it is no longer needed.
<h2><a name="pseudo-rng">Pseudo-Random Number Generator</a></h2>
A pseudo-random number generator is a UniformRandomNumberGenerator
which provides a deterministic sequence of pseudo-random numbers,
based on some algorithm and internal state. Linear congruential and
inversive congruential generators are examples of such pseudo-random
number generators. Often, these generators are very sensitive to
their parameters. In order to prevent wrong implementations from
being used, an external testsuite should check that the generated
sequence and the validation value provided do indeed match.
<p>
Donald E. Knuth gives an extensive overview on pseudo-random number
generation in his book "The Art of Computer Programming, Vol. 2, 3rd
edition, Addison-Wesley, 1997". The descriptions for the specific
generators contain additional references.
<p>
<em>Note:</em> Because the state of a pseudo-random number generator
is necessarily finite, the sequence of numbers returned by the
generator will loop eventually.
<p>
In addition to the UniformRandomNumberGenerator requirements, a
pseudo-random number generator has some additional requirements. In
the following table, <code>X</code> denotes a pseudo-random number
generator class returning objects of type <code>T</code>,
<code>x</code> is a value of <code>T</code>, <code>u</code> is a value
of <code>X</code>, and <code>v</code> is a <code>const</code> value of
<code>X</code>.
<p>
<table border=1>
<tr><th colspan=3 align=center><code>PseudoRandomNumberGenerator</code>
requirements</th></tr>
<tr><td>expression</td><td>return type</td>
<td>pre/post-condition</td></tr>
<tr><td><code>X()</code></td><td>-</td>
<td>creates a generator in some implementation-defined
state. <em>Note:</em> Several generators thusly created may possibly
produce dependent or identical sequences of random numbers.</td></tr>
<tr><td><code>explicit X(...)</code></td><td>-</td>
<td>creates a generator with user-provided state; the implementation
shall specify the constructor argument(s)</td></tr>
<tr><td><code>u.seed(...)</code></td><td>void</td>
<td>sets the current state according to the argument(s); at least
functions with the same signature as the non-default
constructor(s) shall be provided.
<tr><td><code>v.validation(x)</code></td><td><code>bool</code></td>
<td>compares the pre-computed and hardcoded 10001th element in the
generator's random number sequence with <code>x</code>. The generator
must have been constructed by its default constructor and
<code>seed</code> must not have been called for the validation to
be meaningful.
</table>
<p>
<em>Note:</em> The <code>seed</code> member function is similar to the
<code>assign</code> member function in STL containers. However, the
naming did not seem appropriate.
<p>
Classes which model a pseudo-random number generator shall also model
EqualityComparable, i.e. implement <code>operator==</code>. Two
pseudo-random number generators are defined to be <em>equivalent</em>
if they both return an identical sequence of numbers starting from a
given state.
<p>
Classes which model a pseudo-random number generator should also model
the Streamable concept, i.e. implement <code>operator<<</code>
and <code>operator>></code>. If so,
<code>operator<<</code> writes all current state of the
pseudo-random number generator to the given <code>ostream</code> so
that <code>operator>></code> can restore the state at a later
time. The state shall be written in a platform-independent manner,
but it is assumed that the <code>locale</code>s used for writing and
reading be the same.
The pseudo-random number generator with the restored state and the
original at the just-written state shall be equivalent.
<p>
Classes which model a pseudo-random number generator may also model
the CopyConstructible and Assignable concepts. However, note that the
sequences of the original and the copy are strongly correlated (in
fact, they are identical), which may make them unsuitable for some
problem domains. Thus, copying pseudo-random number generators is
discouraged; they should always be passed by (non-<code>const</code>)
reference.
<p>
The classes
<code><a href="random-generators.html#rand48">rand48</a></code>,
<code><a href="random-generators.html#linear_congruential">minstd_rand</a></code>,
and
<code><a href="random-generators.html#mersenne_twister">mt19937</a></code>
are models for a pseudo-random number generator.
<p>
<em>Note:</em> This type of random-number generator is useful for
numerics, games and testing. The non-zero arguments constructor(s)
and the <code>seed()</code> member function(s) allow for a
user-provided state to be installed in the generator. This is useful
for debugging Monte-Carlo algorithms and analyzing particular test
scenarios. The Streamable concept allows to save/restore the state of
the generator, for example to re-run a test suite at a later time.
<h2><a name="quasi-rng">Quasi-Random Number Generators</a></h2>
A quasi-random number generator is a Number Generator which provides a
deterministic sequence of numbers, based on some algorithm and
internal state. The numbers do not have any statistical properties
(such as uniform distribution or independence of successive values).
<p>
<em>Note:</em> Quasi-random number generators are useful for
Monte-Carlo integrations where specially crafted sequences of random
numbers will make the approximation converge faster.
<p>
<em>[Does anyone have a model?]</em>
<p>
<hr>
Jens Maurer, 2000-02-23
</body>
</html>
|
