Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_33_1/libs/random/random-concepts.html @ 20

Last change on this file since 20 was 12, checked in by landauf, 18 years ago

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