Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/random/random-concepts.html @ 69

Last change on this file since 69 was 29, checked in by landauf, 17 years ago

updated boost from 1_33_1 to 1_34_1
File size: 18.2 KB
Line 
1<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
2
3<html>
4<head>
5  <meta http-equiv="Content-Language" content="en-us">
6  <meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
7
8  <title>Boost Random Number Library Concepts</title>
9</head>
10
11<body bgcolor="#FFFFFF" text="#000000">
12  <h1>Random Number Generator Library Concepts</h1>
13
14  <h2>Introduction</h2>
15
16  <p>Random numbers are required in a number of different problem domains,
17  such as</p>
18
19  <ul>
20    <li>numerics (simulation, Monte-Carlo integration)</li>
21
22    <li>games (non-deterministic enemy behavior)</li>
23
24    <li>security (key generation)</li>
25
26    <li>testing (random coverage in white-box tests)</li>
27  </ul>The Boost Random Number Generator Library provides a framework for
28  random number generators with well-defined properties so that the
29  generators can be used in the demanding numerics and security domains. For
30  a general introduction to random numbers in numerics, see
31
32  <blockquote>
33    "Numerical Recipes in C: The art of scientific computing", William H.
34    Press, Saul A. Teukolsky, William A. Vetterling, Brian P. Flannery, 2nd
35    ed., 1992, pp. 274-328
36  </blockquote>Depending on the requirements of the problem domain, different
37  variations of random number generators are appropriate:
38
39  <ul>
40    <li>non-deterministic random number generator</li>
41
42    <li>pseudo-random number generator</li>
43
44    <li>quasi-random number generator</li>
45  </ul>All variations have some properties in common, these concepts (in the
46  STL sense) are called NumberGenerator and UniformRandomNumberGenerator.
47  Each concept will be defined in a subsequent section.
48
49  <p>The goals for this library are the following:</p>
50
51  <ul>
52    <li>allow easy integration of third-party random-number generators</li>
53
54    <li>define a validation interface for the generators</li>
55
56    <li>provide easy-to-use front-end classes which model popular
57    distributions</li>
58
59    <li>provide maximum efficiency</li>
60
61    <li>allow control on quantization effects in front-end processing (not
62    yet done)</li>
63  </ul>
64
65  <h2><a name="number_generator" id="number_generator">Number
66  Generator</a></h2>
67
68  <p>A number generator is a <em>function object</em> (std:20.3
69  [lib.function.objects]) that takes zero arguments. Each call to
70  <code>operator()</code> returns a number. In the following table,
71  <code>X</code> denotes a number generator class returning objects of type
72  <code>T</code>, and <code>u</code> is a value of <code>X</code>.</p>
73
74  <table border="1">
75    <tr>
76      <th colspan="3" align="center"><code>NumberGenerator</code>
77      requirements</th>
78    </tr>
79
80    <tr>
81      <td>expression</td>
82
83      <td>return&nbsp;type</td>
84
85      <td>pre/post-condition</td>
86    </tr>
87
88    <tr>
89      <td><code>X::result_type</code></td>
90
91      <td>T</td>
92
93      <td><code>std::numeric_limits&lt;T&gt;::is_specialized</code> is true,
94      <code>T</code> is <code>LessThanComparable</code></td>
95    </tr>
96
97    <tr>
98      <td><code>u.operator()()</code></td>
99
100      <td>T</td>
101
102      <td>-</td>
103    </tr>
104  </table>
105
106  <p><em>Note:</em> The NumberGenerator requirements do not impose any
107  restrictions on the characteristics of the returned numbers.</p>
108
109  <h2><a name="uniform-rng" id="uniform-rng">Uniform Random Number
110  Generator</a></h2>
111
112  <p>A uniform random number generator is a NumberGenerator that provides a
113  sequence of random numbers uniformly distributed on a given range. The
114  range can be compile-time fixed or available (only) after run-time
115  construction of the object.</p>
116
117  <p>The <em>tight lower bound</em> of some (finite) set S is the (unique)
118  member l in S, so that for all v in S, l &lt;= v holds. Likewise, the
119  <em>tight upper bound</em> of some (finite) set S is the (unique) member u
120  in S, so that for all v in S, v &lt;= u holds.</p>
121
122  <p>In the following table, <code>X</code> denotes a number generator class
123  returning objects of type <code>T</code>, and <code>v</code> is a const
124  value of <code>X</code>.</p>
125
126  <table border="1">
127    <tr>
128      <th colspan="3" align="center">
129      <code>UniformRandomNumberGenerator</code> requirements</th>
130    </tr>
131
132    <tr>
133      <td>expression</td>
134
135      <td>return&nbsp;type</td>
136
137      <td>pre/post-condition</td>
138    </tr>
139
140    <tr>
141      <td><code>X::has_fixed_range</code></td>
142
143      <td><code>bool</code></td>
144
145      <td>compile-time constant; if <code>true</code>, the range on which the
146      random numbers are uniformly distributed is known at compile-time and
147      members <code>min_value</code> and <code>max_value</code> exist.
148      <em>Note:</em> This flag may also be <code>false</code> due to compiler
149      limitations.</td>
150    </tr>
151
152    <tr>
153      <td><code>X::min_value</code></td>
154
155      <td><code>T</code></td>
156
157      <td>compile-time constant; <code>min_value</code> is equal to
158      <code>v.min()</code></td>
159    </tr>
160
161    <tr>
162      <td><code>X::max_value</code></td>
163
164      <td><code>T</code></td>
165
166      <td>compile-time constant; <code>max_value</code> is equal to
167      <code>v.max()</code></td>
168    </tr>
169
170    <tr>
171      <td><code>v.min()</code></td>
172
173      <td><code>T</code></td>
174
175      <td>tight lower bound on the set of all values returned by
176      <code>operator()</code>. The return value of this function shall not
177      change during the lifetime of the object.</td>
178    </tr>
179
180    <tr>
181      <td><code>v.max()</code></td>
182
183      <td><code>T</code></td>
184
185      <td>if <code>std::numeric_limits&lt;T&gt;::is_integer</code>, tight
186      upper bound on the set of all values returned by
187      <code>operator()</code>, otherwise, the smallest representable number
188      larger than the tight upper bound on the set of all values returned by
189      <code>operator()</code>. In any case, the return value of this function
190      shall not change during the lifetime of the object.</td>
191    </tr>
192  </table>
193
194  <p>The member functions <code>min</code>, <code>max</code>, and
195  <code>operator()</code> shall have amortized constant time complexity.</p>
196
197  <p><em>Note:</em> For integer generators (i.e. integer <code>T</code>), the
198  generated values <code>x</code> fulfill <code>min() &lt;= x &lt;=
199  max()</code>, for non-integer generators (i.e. non-integer <code>T</code>),
200  the generated values <code>x</code> fulfill <code>min() &lt;= x &lt;
201  max()</code>.<br>
202  <em>Rationale:</em> The range description with <code>min</code> and
203  <code>max</code> serves two purposes. First, it allows scaling of the
204  values to some canonical range, such as [0..1). Second, it describes the
205  significant bits of the values, which may be relevant for further
206  processing.<br>
207  The range is a closed interval [min,max] for integers, because the
208  underlying type may not be able to represent the half-open interval
209  [min,max+1). It is a half-open interval [min, max) for non-integers,
210  because this is much more practical for borderline cases of continuous
211  distributions.</p>
212
213  <p><em>Note:</em> The UniformRandomNumberGenerator concept does not require
214  <code>operator()(long)</code> and thus it does not fulfill the
215  RandomNumberGenerator (std:25.2.11 [lib.alg.random.shuffle]) requirements.
216  Use the <a href=
217  "random-misc.html#random_number_generator"><code>random_number_generator</code></a>
218  adapter for that.<br>
219  <em>Rationale:</em> <code>operator()(long)</code> is not provided, because
220  mapping the output of some generator with integer range to a different
221  integer range is not trivial.</p>
222
223  <h2><a name="nondet-rng" id="nondet-rng">Non-deterministic Uniform Random
224  Number Generator</a></h2>
225
226  <p>A non-deterministic uniform random number generator is a
227  UniformRandomNumberGenerator that is based on some stochastic process.
228  Thus, it provides a sequence of truly-random numbers. Examples for such
229  processes are nuclear decay, noise of a Zehner diode, tunneling of quantum
230  particles, rolling a die, drawing from an urn, and tossing a coin.
231  Depending on the environment, inter-arrival times of network packets or
232  keyboard events may be close approximations of stochastic processes.</p>
233
234  <p>The class <code><a href=
235  "nondet_random.html#random_device">random_device</a></code> is a model for
236  a non-deterministic random number generator.</p>
237
238  <p><em>Note:</em> This type of random-number generator is useful for
239  security applications, where it is important to prevent that an outside
240  attacker guesses the numbers and thus obtains your encryption or
241  authentication key. Thus, models of this concept should be cautious not to
242  leak any information, to the extent possible by the environment. For
243  example, it might be advisable to explicitly clear any temporary storage as
244  soon as it is no longer needed.</p>
245
246  <h2><a name="pseudo-rng" id="pseudo-rng">Pseudo-Random Number
247  Generator</a></h2>
248
249  <p>A pseudo-random number generator is a UniformRandomNumberGenerator which
250  provides a deterministic sequence of pseudo-random numbers, based on some
251  algorithm and internal state. Linear congruential and inversive
252  congruential generators are examples of such pseudo-random number
253  generators. Often, these generators are very sensitive to their parameters.
254  In order to prevent wrong implementations from being used, an external
255  testsuite should check that the generated sequence and the validation value
256  provided do indeed match.</p>
257
258  <p>Donald E. Knuth gives an extensive overview on pseudo-random number
259  generation in his book "The Art of Computer Programming, Vol. 2, 3rd
260  edition, Addison-Wesley, 1997". The descriptions for the specific
261  generators contain additional references.</p>
262
263  <p><em>Note:</em> Because the state of a pseudo-random number generator is
264  necessarily finite, the sequence of numbers returned by the generator will
265  loop eventually.</p>
266
267  <p>In addition to the UniformRandomNumberGenerator requirements, a
268  pseudo-random number generator has some additional requirements. In the
269  following table, <code>X</code> denotes a pseudo-random number generator
270  class returning objects of type <code>T</code>, <code>x</code> is a value
271  of <code>T</code>, <code>u</code> is a value of <code>X</code>, and
272  <code>v</code> is a <code>const</code> value of <code>X</code>.</p>
273
274  <table border="1">
275    <tr>
276      <th colspan="3" align="center"><code>PseudoRandomNumberGenerator</code>
277      requirements</th>
278    </tr>
279
280    <tr>
281      <td>expression</td>
282
283      <td>return&nbsp;type</td>
284
285      <td>pre/post-condition</td>
286    </tr>
287
288    <tr>
289      <td><code>X()</code></td>
290
291      <td>-</td>
292
293      <td>creates a generator in some implementation-defined state.
294      <em>Note:</em> Several generators thusly created may possibly produce
295      dependent or identical sequences of random numbers.</td>
296    </tr>
297
298    <tr>
299      <td><code>explicit X(...)</code></td>
300
301      <td>-</td>
302
303      <td>creates a generator with user-provided state; the implementation
304      shall specify the constructor argument(s)</td>
305    </tr>
306
307    <tr>
308      <td><code>u.seed(...)</code></td>
309
310      <td>void</td>
311
312      <td>sets the current state according to the argument(s); at least
313      functions with the same signature as the non-default constructor(s)
314      shall be provided.</td>
315    </tr>
316
317    <tr>
318      <td><code>X::validation(x)</code></td>
319
320      <td><code>bool</code></td>
321
322      <td>compares the pre-computed and hardcoded 10001th element in the
323      generator's random number sequence with <code>x</code>. The generator
324      must have been constructed by its default constructor and
325      <code>seed</code> must not have been called for the validation to be
326      meaningful.</td>
327    </tr>
328  </table>
329
330  <p><em>Note:</em> The <code>seed</code> member function is similar to the
331  <code>assign</code> member function in STL containers. However, the naming
332  did not seem appropriate.</p>
333
334  <p>Classes which model a pseudo-random number generator shall also model
335  EqualityComparable, i.e. implement <code>operator==</code>. Two
336  pseudo-random number generators are defined to be <em>equivalent</em> if
337  they both return an identical sequence of numbers starting from a given
338  state.</p>
339
340  <p>Classes which model a pseudo-random number generator should also model
341  the Streamable concept, i.e. implement <code>operator&lt;&lt;</code> and
342  <code>operator&gt;&gt;</code>. If so, <code>operator&lt;&lt;</code> writes
343  all current state of the pseudo-random number generator to the given
344  <code>ostream</code> so that <code>operator&gt;&gt;</code> can restore the
345  state at a later time. The state shall be written in a platform-independent
346  manner, but it is assumed that the <code>locale</code>s used for writing
347  and reading be the same. The pseudo-random number generator with the
348  restored state and the original at the just-written state shall be
349  equivalent.</p>
350
351  <p>Classes which model a pseudo-random number generator may also model the
352  CopyConstructible and Assignable concepts. However, note that the sequences
353  of the original and the copy are strongly correlated (in fact, they are
354  identical), which may make them unsuitable for some problem domains. Thus,
355  copying pseudo-random number generators is discouraged; they should always
356  be passed by (non-<code>const</code>) reference.</p>
357
358  <p>The classes <code><a href=
359  "random-generators.html#rand48">rand48</a></code>, <code><a href=
360  "random-generators.html#linear_congruential">minstd_rand</a></code>, and
361  <code><a href="random-generators.html#mersenne_twister">mt19937</a></code>
362  are models for a pseudo-random number generator.</p>
363
364  <p><em>Note:</em> This type of random-number generator is useful for
365  numerics, games and testing. The non-zero arguments constructor(s) and the
366  <code>seed()</code> member function(s) allow for a user-provided state to
367  be installed in the generator. This is useful for debugging Monte-Carlo
368  algorithms and analyzing particular test scenarios. The Streamable concept
369  allows to save/restore the state of the generator, for example to re-run a
370  test suite at a later time.</p>
371
372  <h2><a name="random-dist" id="random-dist">Random Distribution</a></h2>
373
374  <p>A radom distribution produces random numbers distributed according to
375  some distribution, given uniformly distributed random values as input. In
376  the following table, <code>X</code> denotes a random distribution class
377  returning objects of type <code>T</code>, <code>u</code> is a value of
378  <code>X</code>, <code>x</code> is a (possibly const) value of
379  <code>X</code>, and <code>e</code> is an lvalue of an arbitrary type that
380  meets the requirements of a uniform random number generator, returning
381  values of type <code>U</code>.</p>
382
383  <table border="1">
384    <tr>
385      <th colspan="4" align="center">Random distribution requirements (in
386      addition to number generator, <code>CopyConstructible</code>, and
387      <code>Assignable</code>)</th>
388    </tr>
389
390    <tr>
391      <td>expression</td>
392
393      <td>return&nbsp;type</td>
394
395      <td>pre/post-condition</td>
396
397      <td>complexity</td>
398    </tr>
399
400    <tr>
401      <td><code>X::input_type</code></td>
402
403      <td>U</td>
404
405      <td>-</td>
406
407      <td>compile-time</td>
408    </tr>
409
410    <tr>
411      <td><code>u.reset()</code></td>
412
413      <td><code>void</code></td>
414
415      <td>subsequent uses of <code>u</code> do not depend on values produced
416      by <code>e</code> prior to invoking <code>reset</code>.</td>
417
418      <td>constant</td>
419    </tr>
420
421    <tr>
422      <td><code>u(e)</code></td>
423
424      <td><code>T</code></td>
425
426      <td>the sequence of numbers returned by successive invocations with the
427      same object <code>e</code> is randomly distributed with some
428      probability density function p(x)</td>
429
430      <td>amortized constant number of invocations of <code>e</code></td>
431    </tr>
432
433    <tr>
434      <td><code>os &lt;&lt; x</code></td>
435
436      <td><code>std::ostream&amp;</code></td>
437
438      <td>writes a textual representation for the parameters and additional
439      internal data of the distribution <code>x</code> to
440      <code>os</code>.<br>
441      post: The <code>os.<em>fmtflags</em></code> and fill character are
442      unchanged.</td>
443
444      <td>O(size of state)</td>
445    </tr>
446
447    <tr>
448      <td><code>is &gt;&gt; u</code></td>
449
450      <td><code>std::istream&amp;</code></td>
451
452      <td>restores the parameters and additional internal data of the
453      distribution <code>u</code>.<br>
454      pre: <code>is</code> provides a textual representation that was
455      previously written by <code>operator&lt;&lt;</code><br>
456      post: The <code>is.<em>fmtflags</em></code> are unchanged.</td>
457
458      <td>O(size of state)</td>
459    </tr>
460  </table>
461
462  <p>Additional requirements: The sequence of numbers produced by repeated
463  invocations of <code>x(e)</code> does not change whether or not <code>os
464  &lt;&lt; x</code> is invoked between any of the invocations
465  <code>x(e)</code>. If a textual representation is written using <code>os
466  &lt;&lt; x</code> and that representation is restored into the same or a
467  different object <code>y</code> of the same type using <code>is &gt;&gt;
468  y</code>, repeated invocations of <code>y(e)</code> produce the same
469  sequence of random numbers as would repeated invocations of
470  <code>x(e)</code>.</p>
471
472  <h2><a name="quasi-rng" id="quasi-rng">Quasi-Random Number
473  Generators</a></h2>
474
475  <p>A quasi-random number generator is a Number Generator which provides a
476  deterministic sequence of numbers, based on some algorithm and internal
477  state. The numbers do not have any statistical properties (such as uniform
478  distribution or independence of successive values).</p>
479
480  <p><em>Note:</em> Quasi-random number generators are useful for Monte-Carlo
481  integrations where specially crafted sequences of random numbers will make
482  the approximation converge faster.</p>
483
484  <p><em>[Does anyone have a model?]</em></p>
485  <hr>
486
487  <p><a href="http://validator.w3.org/check?uri=referer"><img border="0" src=
488  "http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01 Transitional"
489  height="31" width="88"></a></p>
490
491  <p>Revised
492  <!--webbot bot="Timestamp" s-type="EDITED" s-format="%d %B, %Y" startspan -->05
493  December, 2006<!--webbot bot="Timestamp" endspan i-checksum="38516" --></p>
494
495  <p><i>Copyright &copy; 2000-2003 <a href=
496  "../../people/jens_maurer.htm">Jens Maurer</a></i></p>
497
498  <p><i>Distributed under the Boost Software License, Version 1.0. (See
499  accompanying file <a href="../../LICENSE_1_0.txt">LICENSE_1_0.txt</a> or
500  copy at <a href=
501  "http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt</a>)</i></p>
502</body>
503</html>
Note: See TracBrowser for help on using the repository browser.