<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta http-equiv="Content-Language" content="en-us">
<meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
<title>Boost Random Number Library Concepts</title>
</head>
<body bgcolor="#FFFFFF" text="#000000">
<h1>Random Number Generator Library Concepts</h1>
<h2>Introduction</h2>
<p>Random numbers are required in a number of different problem domains,
such as</p>
<ul>
<li>numerics (simulation, Monte-Carlo integration)</li>
<li>games (non-deterministic enemy behavior)</li>
<li>security (key generation)</li>
<li>testing (random coverage in white-box tests)</li>
</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>
<li>pseudo-random number generator</li>
<li>quasi-random number generator</li>
</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:</p>
<ul>
<li>allow easy integration of third-party random-number generators</li>
<li>define a validation interface for the generators</li>
<li>provide easy-to-use front-end classes which model popular
distributions</li>
<li>provide maximum efficiency</li>
<li>allow control on quantization effects in front-end processing (not
yet done)</li>
</ul>
<h2><a name="number_generator" id="number_generator">Number
Generator</a></h2>
<p>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.</p>
<h2><a name="uniform-rng" id="uniform-rng">Uniform Random Number
Generator</a></h2>
<p>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>
<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>
<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.</td>
</tr>
</table>
<p>The member functions <code>min</code>, <code>max</code>, and
<code>operator()</code> shall have amortized constant time complexity.</p>
<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>
<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.</p>
<h2><a name="nondet-rng" id="nondet-rng">Non-deterministic Uniform Random
Number Generator</a></h2>
<p>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>
<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>
<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.</p>
<h2><a name="pseudo-rng" id="pseudo-rng">Pseudo-Random Number
Generator</a></h2>
<p>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>
<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>
<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>
<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.</td>
</tr>
<tr>
<td><code>X::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.</td>
</tr>
</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>
<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>
<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>
<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>
<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>
<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.</p>
<h2><a name="random-dist" id="random-dist">Random Distribution</a></h2>
<p>A random distribution produces random numbers distributed according to
some distribution, given uniformly distributed random values as input. In
the following table, <code>X</code> denotes a random distribution class
returning objects of type <code>T</code>, <code>u</code> is a value of
<code>X</code>, <code>x</code> is a (possibly const) value of
<code>X</code>, and <code>e</code> is an lvalue of an arbitrary type that
meets the requirements of a uniform random number generator, returning
values of type <code>U</code>.</p>
<table border="1">
<tr>
<th colspan="4" align="center">Random distribution requirements (in
addition to number generator, <code>CopyConstructible</code>, and
<code>Assignable</code>)</th>
</tr>
<tr>
<td>expression</td>
<td>return type</td>
<td>pre/post-condition</td>
<td>complexity</td>
</tr>
<tr>
<td><code>X::input_type</code></td>
<td>U</td>
<td>-</td>
<td>compile-time</td>
</tr>
<tr>
<td><code>u.reset()</code></td>
<td><code>void</code></td>
<td>subsequent uses of <code>u</code> do not depend on values produced
by <code>e</code> prior to invoking <code>reset</code>.</td>
<td>constant</td>
</tr>
<tr>
<td><code>u(e)</code></td>
<td><code>T</code></td>
<td>the sequence of numbers returned by successive invocations with the
same object <code>e</code> is randomly distributed with some
probability density function p(x)</td>
<td>amortized constant number of invocations of <code>e</code></td>
</tr>
<tr>
<td><code>os << x</code></td>
<td><code>std::ostream&</code></td>
<td>writes a textual representation for the parameters and additional
internal data of the distribution <code>x</code> to
<code>os</code>.<br>
post: The <code>os.<em>fmtflags</em></code> and fill character are
unchanged.</td>
<td>O(size of state)</td>
</tr>
<tr>
<td><code>is >> u</code></td>
<td><code>std::istream&</code></td>
<td>restores the parameters and additional internal data of the
distribution <code>u</code>.<br>
pre: <code>is</code> provides a textual representation that was
previously written by <code>operator<<</code><br>
post: The <code>is.<em>fmtflags</em></code> are unchanged.</td>
<td>O(size of state)</td>
</tr>
</table>
<p>Additional requirements: The sequence of numbers produced by repeated
invocations of <code>x(e)</code> does not change whether or not <code>os
<< x</code> is invoked between any of the invocations
<code>x(e)</code>. If a textual representation is written using <code>os
<< x</code> and that representation is restored into the same or a
different object <code>y</code> of the same type using <code>is >>
y</code>, repeated invocations of <code>y(e)</code> produce the same
sequence of random numbers as would repeated invocations of
<code>x(e)</code>.</p>
<h2><a name="quasi-rng" id="quasi-rng">Quasi-Random Number
Generators</a></h2>
<p>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>
<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>
<p><em>[Does anyone have a model?]</em></p>
<hr>
<p><a href="http://validator.w3.org/check?uri=referer"><img border="0" src=
"../../doc/images/valid-html401.png" alt="Valid HTML 4.01 Transitional"
height="31" width="88"></a></p>
<p>Revised
<!--webbot bot="Timestamp" s-type="EDITED" s-format="%d %B, %Y" startspan -->05
December, 2006<!--webbot bot="Timestamp" endspan i-checksum="38516" --></p>
<p><i>Copyright © 2000-2003 <a href=
"http://www.boost.org/people/jens_maurer.htm">Jens Maurer</a></i></p>
<p><i>Distributed under the Boost Software License, Version 1.0. (See
accompanying file <a href="../../LICENSE_1_0.txt">LICENSE_1_0.txt</a> or
copy at <a href=
"http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt</a>)</i></p>
</body>
</html>
