Boost-Commit :

Date view	Thread view	Subject view	Author view

Subject: [Boost-commit] svn:boost r60172 - in trunk: doc doc/html doc/src libs/random libs/random/doc
From: steven_at_[hidden]
Date: 2010-03-04 23:59:18

Author: steven_watanabe
Date: 2010-03-04 23:59:16 EST (Thu, 04 Mar 2010)
New Revision: 60172
URL: http://svn.boost.org/trac/boost/changeset/60172

Log:
Link new Boost.Random documentation into the main doc build and remove the old html
Added:
   trunk/doc/html/boost_random.html (contents, props changed)
   trunk/libs/random/index.html (contents, props changed)
Removed:
   trunk/libs/random/nondet_random.html
   trunk/libs/random/random-concepts.html
   trunk/libs/random/random-distributions.html
   trunk/libs/random/random-generators.html
   trunk/libs/random/random-misc.html
   trunk/libs/random/random-performance.html
   trunk/libs/random/random-variate.html
   trunk/libs/random/wg21-proposal.html
Text files modified:
   trunk/doc/Jamfile.v2 | 2 ++
   trunk/doc/src/boost.xml | 11 +----------
   trunk/libs/random/doc/Jamfile.v2 | 11 ++++++-----
   3 files changed, 9 insertions(+), 15 deletions(-)

Modified: trunk/doc/Jamfile.v2
==============================================================================
--- trunk/doc/Jamfile.v2 (original)
+++ trunk/doc/Jamfile.v2 2010-03-04 23:59:16 EST (Thu, 04 Mar 2010)
@@ -49,6 +49,7 @@
     <dependency>../libs/unordered/doc//unordered
     <dependency>../libs/thread/doc//thread
     <dependency>../libs/signals2/doc//hello_world_def_code_snippet.xml
+ <dependency>../libs/random/doc//random

     ## Add path references to the QuickBook generated docs...

@@ -71,6 +72,7 @@
     <implicit-dependency>../libs/unordered/doc//unordered
     <implicit-dependency>../libs/thread/doc//thread
     <implicit-dependency>../libs/signals2/doc//hello_world_def_code_snippet.xml
+ <implicit-dependency>../libs/random/doc//random

     <xsl:param>boost.libraries=../../libs/libraries.htm

Added: trunk/doc/html/boost_random.html
==============================================================================
--- (empty file)
+++ trunk/doc/html/boost_random.html 2010-03-04 23:59:16 EST (Thu, 04 Mar 2010)
@@ -0,0 +1,17 @@
+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
+<html>
+ <head>
+ 
+ <title>Redirect to generated documentation</title>
+ <meta http-equiv="refresh" content="0; URL=http://boost-sandbox.sourceforge.net/doc/html/boost_random.html">
+ </head>
+ <body>
+ Automatic redirection failed, please go to
+ http://boost-sandbox.sourceforge.net/doc/html/boost_random.html
+ </body>
+</html>
+

Modified: trunk/doc/src/boost.xml
==============================================================================
--- trunk/doc/src/boost.xml (original)
+++ trunk/doc/src/boost.xml 2010-03-04 23:59:16 EST (Thu, 04 Mar 2010)
@@ -551,16 +551,7 @@
      </libraryinfo>
    </library>

- <library name="Random" dirname="random" html-only="1">
- <libraryinfo>
- <author>
- <firstname>Jens</firstname>
- <surname>Maurer</surname>
- </author>
- <librarypurpose>A complete system for random number generation</librarypurpose>
- <librarycategory name="category:math"/>
- </libraryinfo>
- </library>
+ <xi:include href="random.xml"/>

    <library name="Rational" dirname="rational" html-only="1">
      <libraryinfo>

Modified: trunk/libs/random/doc/Jamfile.v2
==============================================================================
--- trunk/libs/random/doc/Jamfile.v2 (original)
+++ trunk/libs/random/doc/Jamfile.v2 2010-03-04 23:59:16 EST (Thu, 04 Mar 2010)
@@ -47,10 +47,12 @@
# temporary hack for local docs
local BOOST_ROOT = ../../../.. ;

+path-constant here : . ;
+
doxygen reference :
- ../../../boost/random/$(doxygen_files).hpp
- ../../../boost/nondet_random.hpp
- ../../../boost/random.hpp
+ $(here)/../../../boost/random/$(doxygen_files).hpp
+ $(here)/../../../boost/nondet_random.hpp
+ $(here)/../../../boost/random.hpp
   :
     <doxygen:param>EXPAND_ONLY_PREDEF=YES
     <doxygen:param>"ALIASES= \\
@@ -58,7 +60,6 @@
         endxmlnote=\"@xmlonly </para></note> @endxmlonly\" \\
         blockquote=\"@xmlonly <blockquote><para> @endxmlonly\" \\
         endblockquote=\"@xmlonly </para></blockquote> @endxmlonly\" \\
- boost=\"$(BOOST_ROOT)\" \\
         random_distribution=\"@xmlonly <link linkend=\\\"boost_random.reference.concepts.random_distribution\\\">random distribution</link> @endxmlonly\" \\
         pseudo_random_number_generator=\"@xmlonly <link linkend=\\\"boost_random.reference.concepts.pseudo_random_number_generator\\\">pseudo-random number generator</link> @endxmlonly\" \\
         uniform_random_number_generator=\"@xmlonly <link linkend=\\\"boost_random.reference.concepts.uniform_random_number_generator\\\">uniform random number generator</link> @endxmlonly\" \\
@@ -102,7 +103,7 @@
     <doxygen:xml-imagedir>images/random
;

-xml random : random.qbk ;
+xml random : random.qbk : <dependency>reference ;

boostbook standalone :
     random

Added: trunk/libs/random/index.html
==============================================================================
--- (empty file)
+++ trunk/libs/random/index.html 2010-03-04 23:59:16 EST (Thu, 04 Mar 2010)
@@ -0,0 +1,14 @@
+<html>
+ <head>
+ <meta http-equiv="refresh" content="0; URL=../../doc/html/boost_random.html">
+ </head>
+ <body>
+ Automatic redirection failed, please go to
+ ../../doc/html/boost_random.html
+ <p>Copyright (c) 2010 Steven Watanabe</p>
+ <p>Distributed under the Boost Software License, Version 1.0. (See accompanying file
+ LICENSE_1_0.txt or copy at
+ www.boost.org/LICENSE_1_0.txt).
+ </p>
+ </body>
+</html>

Deleted: trunk/libs/random/nondet_random.html
==============================================================================
--- trunk/libs/random/nondet_random.html 2010-03-04 23:59:16 EST (Thu, 04 Mar 2010)
+++ (empty file)
@@ -1,145 +0,0 @@
-<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
-
-<html>
-<head>
- <meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
-
- <title>Boost RNG Library - Non-Deterministic Random Number
- Generators</title>
-</head>
-
-<body bgcolor="#FFFFFF" text="#000000">
- <h1><img src="../../boost.png" alt="boost.png (6897 bytes)" align="middle"
- width="277" height="86">Header <a href=
- "../../boost/nondet_random.hpp"><boost/nondet_random.hpp></a></h1>
-
- <ul>
- <li>Synopsis</li>
-
- <li>Class random_device</li>
-
- <li>Performance</li>
- </ul>
-
- <h2><a name="synopsis" id=
- "synopsis">Header</a><code><boost/nondet_random.hpp></code>
- Synopsis</h2>
- <pre>
-namespace boost {
- class random_device;
-} // namespace boost
-</pre>
-
- <h2><a name="random_device" id="random_device">Class
- <code>random_device</code></a></h2>
-
- <h3>Synopsis</h3>
- <pre>
-class random_device : noncopyable
-{
-public:
- typedef unsigned int result_type;
- static const bool has_fixed_range = true;
- static const result_type min_value = /* implementation defined */;
- static const result_type max_value = /* implementation defined */;
- result_type min() const;
- result_type max() const;
- explicit random_device(const std::string& token = default_token);
- ~random_device();
- double entropy() const;
- unsigned int operator()();
-};
-</pre>
-
- <h3>Description</h3>
-
- <p>Class <code>random_device</code> models a <a href=
- "random-concepts.html#nondet-rng">non-deterministic random number
- generator</a>. It uses one or more implementation-defined stochastic
- processes to generate a sequence of uniformly distributed non-deterministic
- random numbers. For those environments where a non-deterministic random
- number generator is not available, class <code>random_device</code> must
- not be implemented. See</p>
-
- <blockquote>
- "Randomness Recommendations for Security", D. Eastlake, S. Crocker, J.
- Schiller, Network Working Group, RFC 1750, December 1994
- </blockquote>for further discussions.
-
- <p><em>Note:</em> Some operating systems abstract the computer hardware
- enough to make it difficult to non-intrusively monitor stochastic
- processes. However, several do provide a special device for exactly this
- purpose. It seems to be impossible to emulate the functionality using
- Standard C++ only, so users should be aware that this class may not be
- available on all platforms.</p>
-
- <h3>Members</h3>
- <pre>
-explicit random_device(const std::string& token = default_token)
-</pre><strong>Effects:</strong> Constructs a <code>random_device</code>,
-optionally using the given <code>token</code> as an access specification (for
-example, a URL) to some implementation-defined service for monitoring a
-stochastic process.
- <pre>
- double entropy() const
-</pre><strong>Returns:</strong> An entropy estimate for the random numbers
-returned by operator(), in the range <code>min()</code> to log<sub>2</sub>(
-<code>max()</code>+1). A deterministic random number generator (e.g. a
-pseudo-random number engine) has entropy 0.<br>
- <strong>Throws:</strong> Nothing.
-
- <h3>Implementation Note for Linux</h3>
-
- <p>On the Linux operating system, <code>token</code> is interpreted as a
- filesystem path. It is assumed that this path denotes an operating system
- pseudo-device which generates a stream of non-deterministic random numbers.
- The pseudo-device should never signal an error or end-of-file. Otherwise,
- <code>std::ios_base::failure</code> is thrown. By default,
- <code>random_device</code> uses the <code>/dev/urandom</code> pseudo-device
- to retrieve the random numbers. Another option would be to specify the
- <code>/dev/random</code> pseudo-device, which blocks on reads if the
- entropy pool has no more random bits available.</p>
-
- <h2><a name="performance" id="performance">Performance</a></h2>
-
- <p>The test program <a href=
- "nondet_random_speed.cpp">nondet_random_speed.cpp</a> measures the
- execution times of the <a href=
- "../../boost/nondet_random.hpp">nondet_random.hpp</a> implementation of the
- above algorithms in a tight loop. The performance has been evaluated on a
- Pentium Pro 200 MHz with gcc 2.95.2, Linux 2.2.13, glibc 2.1.2.</p>
-
- <table border="1" summary="">
- <tr>
- <th>class</th>
-
- <th>time per invocation [usec]</th>
- </tr>
-
- <tr>
- <td>random_device</td>
-
- <td>92.0</td>
- </tr>
- </table>
-
- <p>The measurement error is estimated at +/- 1 usec.</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
- 05
- December, 2006</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 LICENSE_1_0.txt or
- copy at <a href=
- "http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt>)</i></p>
-</body>
-</html>

Deleted: trunk/libs/random/random-concepts.html
==============================================================================
--- trunk/libs/random/random-concepts.html 2010-03-04 23:59:16 EST (Thu, 04 Mar 2010)
+++ (empty file)
@@ -1,503 +0,0 @@
-<!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>mt19937</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
- 05
- December, 2006</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 LICENSE_1_0.txt or
- copy at <a href=
- "http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt>)</i></p>
-</body>
-</html>

Deleted: trunk/libs/random/random-distributions.html
==============================================================================
--- trunk/libs/random/random-distributions.html 2010-03-04 23:59:16 EST (Thu, 04 Mar 2010)
+++ (empty file)
@@ -1,861 +0,0 @@
-<!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 Distributions</title>
-</head>
-
-<body bgcolor="#FFFFFF" text="#000000">
- <h1>Random Number Library Distributions</h1>
-
- <ul>
- <li>Introduction</li>
-
- <li>Synopsis</li>
-
- <li><a href="#uniform_smallint">Class template
- <code>uniform_smallint</code></a></li>
-
- <li><a href="#uniform_int">Class template
- <code>uniform_int</code></a></li>
-
- <li>Class template uniform_01</li>
-
- <li><a href="#uniform_real">Class template
- <code>uniform_real</code></a></li>
-
- <li><a href="#bernoulli_distribution">Class template
- <code>bernoulli_distribution</code></a></li>
-
- <li><a href="#geometric_distribution">Class template
- <code>geometric_distribution</code></a></li>
-
- <li><a href="#triangle_distribution">Class template
- <code>triangle_distribution</code></a></li>
-
- <li><a href="#exponential_distribution">Class template
- <code>exponential_distribution</code></a></li>
-
- <li><a href="#normal_distribution">Class template
- <code>normal_distribution</code></a></li>
-
- <li><a href="#lognormal_distribution">Class template
- <code>lognormal_distribution</code></a></li>
-
- <li><a href="#uniform_on_sphere">Class template
- <code>uniform_on_sphere</code></a></li>
- </ul>
-
- <h2><a name="intro" id="intro">Introduction</a></h2>
-
- <p>In addition to the <a href="random-generators.html">random number
- generators</a>, this library provides distribution functions which map one
- distribution (often a uniform distribution provided by some generator) to
- another.</p>
-
- <p>Usually, there are several possible implementations of any given
- mapping. Often, there is a choice between using more space, more
- invocations of the underlying source of random numbers, or more
- time-consuming arithmetic such as trigonometric functions. This interface
- description does not mandate any specific implementation. However,
- implementations which cannot reach certain values of the specified
- distribution or otherwise do not converge statistically to it are not
- acceptable.</p>
-
- <table border="1" summary="">
- <tr>
- <th>distribution</th>
-
- <th>explanation</th>
-
- <th>example</th>
- </tr>
-
- <tr>
- <td><code>uniform_smallint</code></td>
-
- <td>discrete uniform distribution on a small set of integers (much
- smaller than the range of the underlying generator)</td>
-
- <td>drawing from an urn</td>
- </tr>
-
- <tr>
- <td><code>uniform_int</code></td>
-
- <td>discrete uniform distribution on a set of integers; the underlying
- generator may be called several times to gather enough randomness for
- the output</td>
-
- <td>drawing from an urn</td>
- </tr>
-
- <tr>
- <td><code>uniform_01</code></td>
-
- <td>continuous uniform distribution on the range [0,1); important basis
- for other distributions</td>
-
- <td>-</td>
- </tr>
-
- <tr>
- <td><code>uniform_real</code></td>
-
- <td>continuous uniform distribution on some range [min, max) of real
- numbers</td>
-
- <td>for the range [0, 2pi): randomly dropping a stick and measuring its
- angle in radiants (assuming the angle is uniformly distributed)</td>
- </tr>
-
- <tr>
- <td><code><a href=
- "#bernoulli_distribution">bernoulli_distribution</a></code></td>
-
- <td>Bernoulli experiment: discrete boolean valued distribution with
- configurable probability</td>
-
- <td>tossing a coin (p=0.5)</td>
- </tr>
-
- <tr>
- <td><code><a href=
- "#geometric_distribution">geometric_distribution</a></code></td>
-
- <td>measures distance between outcomes of repeated Bernoulli
- experiments</td>
-
- <td>throwing a die several times and counting the number of tries until
- a "6" appears for the first time</td>
- </tr>
-
- <tr>
- <td><code><a href=
- "#triangle_distribution">triangle_distribution</a></code></td>
-
- <td>?</td>
-
- <td>?</td>
- </tr>
-
- <tr>
- <td><code><a href=
- "#exponential_distribution">exponential_distribution</a></code></td>
-
- <td>exponential distribution</td>
-
- <td>measuring the inter-arrival time of alpha particles emitted by
- radioactive matter</td>
- </tr>
-
- <tr>
- <td><code><a href=
- "#normal_distribution">normal_distribution</a></code></td>
-
- <td>counts outcomes of (infinitely) repeated Bernoulli experiments</td>
-
- <td>tossing a coin 10000 times and counting how many front sides are
- shown</td>
- </tr>
-
- <tr>
- <td><code><a href=
- "#lognormal_distribution">lognormal_distribution</a></code></td>
-
- <td>lognormal distribution (sometimes used in simulations)</td>
-
- <td>measuring the job completion time of an assembly line worker</td>
- </tr>
-
- <tr>
- <td><code><a href=
- "#uniform_on_sphere">uniform_on_sphere</a></code></td>
-
- <td>uniform distribution on a unit sphere of arbitrary dimension</td>
-
- <td>choosing a random point on Earth (assumed to be a sphere) where to
- spend the next vacations</td>
- </tr>
- </table>
-
- <p>The template parameters of the distribution functions are always in the
- order</p>
-
- <ul>
- <li>Underlying source of random numbers</li>
-
- <li>If applicable, return type, with a default to a reasonable type.</li>
- </ul>
-
- <p><em>The distribution functions no longer satisfy the input iterator
- requirements (std:24.1.1 [lib.input.iterators]), because this is redundant
- given the Generator interface and imposes a run-time overhead on all users.
- Moreover, a Generator interface appeals to random number generation as
- being more "natural". Use an <a href=
- "../utility/iterator_adaptors.htm">iterator adaptor</a> if you need to wrap
- any of the generators in an input iterator interface.</em></p>
-
- <p>All of the distribution functions described below store a non-const
- reference to the underlying source of random numbers. Therefore, the
- distribution functions are not Assignable. However, they are
- CopyConstructible. Copying a distribution function will copy the parameter
- values. Furthermore, both the copy and the original will refer to the same
- underlying source of random numbers. Therefore, both the copy and the
- original will obtain their underlying random numbers from a single
- sequence.</p>
-
- <p>In this description, I have refrained from documenting those members in
- detail which are already defined in the <a href=
- "random-concepts.html">concept documentation</a>.</p>
-
- <h2><a name="synopsis" id="synopsis">Synopsis of the distributions</a>
- available from header <code><boost/random.hpp></code></h2>
- <pre>
-namespace boost {
- template<class IntType = int>
- class uniform_smallint;
- template<class IntType = int>
- class uniform_int;
- template<class RealType = double>
- class uniform_01;
- template<class RealType = double>
- class uniform_real;
-
- // discrete distributions
- template<class RealType = double>
- class bernoulli_distribution;
- template<class IntType = int>
- class geometric_distribution;
-
- // continuous distributions
- template<class RealType = double>
- class triangle_distribution;
- template<class RealType = double>
- class exponential_distribution;
- template<class RealType = double>
- class normal_distribution;
- template<class RealType = double>
- class lognormal_distribution;
- template<class RealType = double,
- class Cont = std::vector<RealType> >
- class uniform_on_sphere;
-}
-</pre>
-
- <h2><a name="uniform_smallint" id="uniform_smallint">Class template
- <code>uniform_smallint</code></a></h2>
-
- <h3>Synopsis</h3>
- <pre>
-#include <<a href=
-"../../boost/random/uniform_smallint.hpp">boost/random/uniform_smallint.hpp</a>>
-
-template<class IntType = int>
-class uniform_smallint
-{
-public:
- typedef IntType input_type;
- typedef IntType result_type;
- static const bool has_fixed_range = false;
- uniform_smallint(IntType min, IntType max);
- result_type min() const;
- result_type max() const;
- void reset();
- template<class UniformRandomNumberGenerator>
- result_type operator()(UniformRandomNumberGenerator& urng);
-};
-</pre>
-
- <h3>Description</h3>
-
- <p>The distribution function <code>uniform_smallint</code> models a
- random distribution. On each
- invocation, it returns a random integer value uniformly distributed in the
- set of integer numbers {min, min+1, min+2, ..., max}. It assumes that the
- desired range (max-min+1) is small compared to the range of the underlying
- source of random numbers and thus makes no attempt to limit quantization
- errors.</p>
-
- <p>Let r<sub>out</sub>=(max-min+1) the desired range of integer numbers,
- and let r<sub>base</sub> be the range of the underlying source of random
- numbers. Then, for the uniform distribution, the theoretical probability
- for any number i in the range r<sub>out</sub> will be p<sub>out</sub>(i) =
- 1/r<sub>out</sub>. Likewise, assume a uniform distribution on
- r<sub>base</sub> for the underlying source of random numbers, i.e.
- p<sub>base</sub>(i) = 1/r<sub>base</sub>. Let p<sub>out_s</sub>(i) denote
- the random distribution generated by <code>uniform_smallint</code>. Then
- the sum over all i in r<sub>out</sub> of
- (p<sub>out_s</sub>(i)/p<sub>out</sub>(i) -1)<sup>2</sup> shall not exceed
- r<sub>out</sub>/r<sub>base</sub><sup>2</sup> (r<sub>base</sub> mod
- r<sub>out</sub>)(r<sub>out</sub> - r<sub>base</sub> mod
- r<sub>out</sub>).</p>
-
- <p>The template parameter <code>IntType</code> shall denote an integer-like
- value type.</p>
-
- <p><em>Note:</em> The property above is the square sum of the relative
- differences in probabilities between the desired uniform distribution
- p<sub>out</sub>(i) and the generated distribution p<sub>out_s</sub>(i). The
- property can be fulfilled with the calculation (base_rng mod
- r<sub>out</sub>), as follows: Let r = r<sub>base</sub> mod r<sub>out</sub>.
- The base distribution on r<sub>base</sub> is folded onto the range
- r<sub>out</sub>. The numbers i < r have assigned (r<sub>base</sub> div
- r<sub>out</sub>)+1 numbers of the base distribution, the rest has only
- (r<sub>base</sub> div r<sub>out</sub>). Therefore, p<sub>out_s</sub>(i) =
- ((r<sub>base</sub> div r<sub>out</sub>)+1) / r<sub>base</sub> for i < r
- and p<sub>out_s</sub>(i) = (r<sub>base</sub> div
- r<sub>out</sub>)/r<sub>base</sub> otherwise. Substituting this in the above
- sum formula leads to the desired result.</p>
-
- <p><em>Note:</em> The upper bound for (r<sub>base</sub> mod
- r<sub>out</sub>)(r<sub>out</sub> - r<sub>base</sub> mod r<sub>out</sub>) is
- r<sub>out</sub><sup>2</sup>/4. Regarding the upper bound for the square sum
- of the relative quantization error of
- r<sub>out</sub><sup>3</sup>/(4*r<sub>base</sub><sup>2</sup>), it seems wise
- to either choose r<sub>base</sub> so that r<sub>base</sub> >
- 10*r<sub>out</sub><sup>2</sup> or ensure that r<sub>base</sub> is divisible
- by r<sub>out</sub>.</p>
-
- <h3>Members</h3>
- <pre>
-uniform_smallint(IntType min, IntType max)
-</pre>
-
- <p><strong>Effects:</strong> Constructs a <code>uniform_smallint</code>
- functor. <code>min</code> and <code>max</code> are the lower and upper
- bounds of the output range, respectively.</p>
-
- <h2><a name="uniform_int" id="uniform_int">Class template
- <code>uniform_int</code></a></h2>
-
- <h3>Synopsis</h3>
- <pre>
-#include <<a href=
-"../../boost/random/uniform_int.hpp">boost/random/uniform_int.hpp</a>>
-
-template<class IntType = int>
-class uniform_int
-{
-public:
- typedef IntType input_type;
- typedef IntType result_type;
- static const bool has_fixed_range = false;
- explicit uniform_int(IntType min = 0, IntType max = 9);
- result_type min() const;
- result_type max() const;
- void reset();
- template<class UniformRandomNumberGenerator>
- result_type operator()(UniformRandomNumberGenerator& urng);
- template<class UniformRandomNumberGenerator>
- result_type operator()(UniformRandomNumberGenerator& urng, result_type n);
-};
-</pre>
-
- <h3>Description</h3>
-
- <p>The distribution function <code>uniform_int</code> models a <a href=
- "random-concepts.html#random-dist">random distribution</a>. On each
- invocation, it returns a random integer value uniformly distributed in the
- set of integer numbers {min, min+1, min+2, ..., max}.</p>
-
- <p>The template parameter <code>IntType</code> shall denote an integer-like
- value type.</p>
-
- <h3>Members</h3>
- <pre>
- uniform_int(IntType min = 0, IntType max = 9)
-</pre>
-
- <p><strong>Requires:</strong> min <= max<br>
- <strong>Effects:</strong> Constructs a <code>uniform_int</code> object.
- <code>min</code> and <code>max</code> are the parameters of the
- distribution.</p>
- <pre>
- result_type min() const
-</pre>
-
- <p><strong>Returns:</strong> The "min" parameter of the distribution.</p>
- <pre>
- result_type max() const
-</pre>
-
- <p><strong>Returns:</strong> The "max" parameter of the distribution.</p>
- <pre>
- result_type operator()(UniformRandomNumberGenerator& urng, result_type
-n)
-</pre>
-
- <p><strong>Returns:</strong> A uniform random number x in the range 0 <=
- x < n. <em>[Note: This allows a <code>variate_generator</code> object
- with a <code>uniform_int</code> distribution to be used with
- std::random_shuffe, see [lib.alg.random.shuffle]. ]</em></p>
-
- <h2><a name="uniform_01" id="uniform_01">Class template
- <code>uniform_01</code></a></h2>
-
- <h3>Synopsis</h3>
- <pre>
-#include <<a href=
-"../../boost/random/uniform_01.hpp">boost/random/uniform_01.hpp</a>>
-
-template<class UniformRandomNumberGenerator, class RealType = double>
-class uniform_01
-{
-public:
- typedef UniformRandomNumberGenerator base_type;
- typedef RealType result_type;
- static const bool has_fixed_range = false;
- explicit uniform_01(base_type rng);
- result_type operator()();
- result_type min() const;
- result_type max() const;
-};
-</pre>
-
- <h3>Description</h3>
-
- <p>The distribution function <code>uniform_01</code> models a <a href=
- "random-concepts.html#random-dist">random distribution</a>. On each
- invocation, it returns a random floating-point value uniformly distributed
- in the range [0..1). The value is computed using
- <code>std::numeric_limits<RealType>::digits</code> random binary
- digits, i.e. the mantissa of the floating-point value is completely filled
- with random bits. [<em>Note:</em> Should this be configurable?]</p>
-
- <p><em>WARNING:</em> As an exception / historic accident, this class
- takes a UniformRandomNumberGenerator as its constructor parameter,
- and BY VALUE. Usually, you want reference semantics so that the
- state of the passed-in generator is changed in-place and not copied.
- In that case, explicitly supply a reference type for the template
- parameter UniformRandomNumberGenerator.</p>
-
- <p>The template parameter <code>RealType</code> shall denote a float-like
- value type with support for binary operators +, -, and /. It must be large
- enough to hold floating-point numbers of value
- <code>rng.max()-rng.min()+1</code>.</p>
-
- <p><code>base_type::result_type</code> must be a number-like value type, it
- must support <code>static_cast<></code> to <code>RealType</code> and
- binary operator -.</p>
-
- <p><em>Note:</em> The current implementation is buggy, because it may not
- fill all of the mantissa with random bits. I'm unsure how to fill a
- (to-be-invented) <code>boost::bigfloat</code> class with random bits
- efficiently. It's probably time for a traits class.</p>
-
- <h3>Members</h3>
- <pre>
-explicit uniform_01(base_type rng)
-</pre>
-
- <p><strong>Effects:</strong> Constructs a <code>uniform_01</code> functor
- with the given uniform random number generator as the underlying source of
- random numbers.</p>
-
- <h2><a name="uniform_real" id="uniform_real">Class template
- <code>uniform_real</code></a></h2>
-
- <h3>Synopsis</h3>
- <pre>
-#include <<a href=
-"../../boost/random/uniform_real.hpp">boost/random/uniform_real.hpp</a>>
-
-template<class RealType = double>
-class uniform_real
-{
-public:
- typedef RealType input_type;
- typedef RealType result_type;
- static const bool has_fixed_range = false;
- uniform_real(RealType min = RealType(0), RealType max = RealType(1));
- result_type min() const;
- result_type max() const;
- void reset();
- template<class UniformRandomNumberGenerator>
- result_type operator()(UniformRandomNumberGenerator& urng);
-};
-</pre>
-
- <h3>Description</h3>
-
- <p>The distribution function <code>uniform_real</code> models a <a href=
- "random-concepts.html#random-dist">random distribution</a>. On each
- invocation, it returns a random floating-point value uniformly distributed
- in the range [min..max). The value is computed using
- <code>std::numeric_limits<RealType>::digits</code> random binary
- digits, i.e. the mantissa of the floating-point value is completely filled
- with random bits.</p>
-
- <p><em>Note:</em> The current implementation is buggy, because it may not
- fill all of the mantissa with random bits.</p>
-
- <h3>Members</h3>
- <pre>
- uniform_real(RealType min = RealType(0), RealType max = RealType(1))
-</pre>
-
- <p><strong>Requires:</strong> min <= max<br>
- <strong>Effects:</strong> Constructs a <code>uniform_real</code> object;
- <code>min</code> and <code>max</code> are the parameters of the
- distribution.</p>
- <pre>
- result_type min() const
-</pre>
-
- <p><strong>Returns:</strong> The "min" parameter of the distribution.</p>
- <pre>
- result_type max() const
-</pre>
-
- <p><strong>Returns:</strong> The "max" parameter of the distribution.</p>
-
- <h2><a name="bernoulli_distribution" id="bernoulli_distribution">Class
- template <code>bernoulli_distribution</code></a></h2>
-
- <h3>Synopsis</h3>
- <pre>
-#include <<a href=
-"../../boost/random/bernoulli_distribution.hpp">boost/random/bernoulli_distribution.hpp</a>>
-
-template<class RealType = double>
-class bernoulli_distribution
-{
-public:
- typedef int input_type;
- typedef bool result_type;
-
- explicit bernoulli_distribution(const RealType& p = RealType(0.5));
- RealType p() const;
- void reset();
- template<class UniformRandomNumberGenerator>
- result_type operator()(UniformRandomNumberGenerator& urng);
-};
-</pre>
-
- <h3>Description</h3>
-
- <p>Instantiations of class template <code>bernoulli_distribution</code>
- model a random distribution.
- Such a random distribution produces <code>bool</code> values distributed
- with probabilities P(true) = p and P(false) = 1-p. p is the parameter of
- the distribution.</p>
-
- <h3>Members</h3>
- <pre>
- bernoulli_distribution(const RealType& p = RealType(0.5))
-</pre>
-
- <p><strong>Requires:</strong> 0 <= p <= 1<br>
- <strong>Effects:</strong> Constructs a <code>bernoulli_distribution</code>
- object. <code>p</code> is the parameter of the distribution.</p>
- <pre>
- RealType p() const
-</pre>
-
- <p><strong>Returns:</strong> The "p" parameter of the distribution.</p>
-
- <h2><a name="geometric_distribution" id="geometric_distribution">Class
- template <code>geometric_distribution</code></a></h2>
-
- <h3>Synopsis</h3>
- <pre>
-#include <<a href=
-"../../boost/random/geometric_distribution.hpp">boost/random/geometric_distribution.hpp</a>>
-
-template<class UniformRandomNumberGenerator, class IntType = int>
-class geometric_distribution
-{
-public:
- typedef RealType input_type;
- typedef IntType result_type;
-
- explicit geometric_distribution(const RealType& p = RealType(0.5));
- RealType p() const;
- void reset();
- template<class UniformRandomNumberGenerator>
- result_type operator()(UniformRandomNumberGenerator& urng);
-};
-</pre>
-
- <h3>Description</h3>
-
- <p>Instantiations of class template <code>geometric_distribution</code>
- model a random distribution.
- A <code>geometric_distribution</code> random distribution produces integer
- values <em>i</em> >= 1 with p(i) = (1-p) * p<sup>i-1</sup>. p is the
- parameter of the distribution.
- Each invocation of the UniformRandomNumberGenerator shall result in a
- floating-point value in the range [0,1).</p>
-
- <h3>Members</h3>
- <pre>
- geometric_distribution(const RealType& p = RealType(0.5))
-</pre>
-
- <p><strong>Requires:</strong> 0 < p < 1<br>
- <strong>Effects:</strong> Constructs a <code>geometric_distribution</code>
- object; <code>p</code> is the parameter of the distribution.</p>
- <pre>
- RealType p() const
-</pre>
-
- <p><strong>Returns:</strong> The "p" parameter of the distribution.</p>
-
- <h2><a name="triangle_distribution" id="triangle_distribution">Class
- template <code>triangle_distribution</code></a></h2>
-
- <h3>Synopsis</h3>
- <pre>
-#include <<a href=
-"../../boost/random/triangle_distribution.hpp">boost/random/triangle_distribution.hpp</a>>
-
-template<class RealType = double>
-class triangle_distribution
-{
-public:
- typedef RealType input_type;
- typedef RealType result_type;
- triangle_distribution(result_type a, result_type b, result_type c);
- result_type a() const;
- result_type b() const;
- result_type c() const;
- void reset();
- template<class UniformRandomNumberGenerator>
- result_type operator()(UniformRandomNumberGenerator& urng);
-};
-</pre>
-
- <h3>Description</h3>
-
- <p>Instantiations of class template <code>triangle_distribution</code>
- model a random distribution.
- The returned floating-point values <code>x</code> satisfy <code>a <= x
- <= c</code>; <code>x</code> has a triangle distribution, where
- <code>b</code> is the most probable value for <code>x</code>.
- Each invocation of the UniformRandomNumberGenerator shall result in a
- floating-point value in the range [0,1). </p>
-
- <h3>Members</h3>
- <pre>
-triangle_distribution(result_type a, result_type b, result_type c)
-</pre>
-
- <p><strong>Effects:</strong> Constructs a
- <code>triangle_distribution</code> functor. <code>a, b, c</code> are the
- parameters for the distribution.</p>
-
- <h2><a name="exponential_distribution" id="exponential_distribution">Class
- template <code>exponential_distribution</code></a></h2>
-
- <h3>Synopsis</h3>
- <pre>
-#include <<a href=
-"../../boost/random/exponential_distribution.hpp">boost/random/exponential_distribution.hpp</a>>
-
-template<class RealType = double>
-class exponential_distribution
-{
-public:
- typedef RealType input_type;
- typedef RealType result_type;
- explicit exponential_distribution(const result_type& lambda);
- RealType lambda() const;
- void reset();
- template<class UniformRandomNumberGenerator>
- result_type operator()(UniformRandomNumberGenerator& urng);
-};
-</pre>
-
- <h3>Description</h3>
-
- <p>Instantiations of class template <code>exponential_distribution</code>
- model a random distribution.
- Such a distribution produces random numbers x > 0 distributed with
- probability density function p(x) = lambda * exp(-lambda * x), where lambda
- is the parameter of the distribution.
- Each invocation of the UniformRandomNumberGenerator shall result in a
- floating-point value in the range [0,1). </p>
-
- <h3>Members</h3>
- <pre>
- exponential_distribution(const result_type& lambda = result_type(1))
-</pre>
-
- <p><strong>Requires:</strong> lambda > 0<br>
- <strong>Effects:</strong> Constructs an
- <code>exponential_distribution</code> object with <code>rng</code> as the
- reference to the underlying source of random numbers. <code>lambda</code>
- is the parameter for the distribution.</p>
- <pre>
- RealType lambda() const
-</pre>
-
- <p><strong>Returns:</strong> The "lambda" parameter of the
- distribution.</p>
-
- <h2><a name="normal_distribution" id="normal_distribution">Class template
- <code>normal_distribution</code></a></h2>
-
- <h3>Synopsis</h3>
- <pre>
-#include <<a href=
-"../../boost/random/normal_distribution.hpp">boost/random/normal_distribution.hpp</a>>
-
-template<class RealType = double>
-class normal_distribution
-{
-public:
- typedef RealType input_type;
- typedef RealType result_type;
- explicit normal_distribution(const result_type& mean = 0,
- const result_type& sigma = 1);
- RealType mean() const;
- RealType sigma() const;
- void reset();
- template<class UniformRandomNumberGenerator>
- result_type operator()(UniformRandomNumberGenerator& urng);
-};
-</pre>
-
- <h3>Description</h3>
-
- <p>Instantiations of class template <code>normal_distribution</code> model
- a random distribution. Such
- a distribution produces random numbers x distributed with probability
- density function p(x) = 1/sqrt(2*pi*sigma) * exp(- (x-mean)<sup>2</sup> /
- (2*sigma<sup>2</sup>) ), where mean and sigma are the parameters of the
- distribution. Each invocation of the UniformRandomNumberGenerator shall
- result in a floating-point value in the range [0,1).</p>
-
- <h3>Members</h3>
- <pre>
- explicit normal_distribution(const result_type& mean = 0,
- const result_type& sigma = 1);
-</pre>
-
- <p><strong>Requires:</strong> sigma > 0<br>
- <strong>Effects:</strong> Constructs a <code>normal_distribution</code>
- object; <code>mean</code> and <code>sigma</code> are the parameters for the
- distribution.</p>
- <pre>
- RealType mean() const
-</pre>
-
- <p><strong>Returns:</strong> The "mean" parameter of the distribution.</p>
- <pre>
- RealType sigma() const
-</pre>
-
- <p><strong>Returns:</strong> The "sigma" parameter of the distribution.</p>
-
- <h2><a name="lognormal_distribution" id="lognormal_distribution">Class
- template <code>lognormal_distribution</code></a></h2>
-
- <h3>Synopsis</h3>
- <pre>
-#include <<a href=
-"../../boost/random/lognormal_distribution.hpp">boost/random/lognormal_distribution.hpp</a>>
-
-template<class RealType = double>
-class lognormal_distribution
-{
-public:
- typedef typename normal_distribution<RealType>::input_type
- typedef RealType result_type;
- explicit lognormal_distribution(const result_type& mean = 1.0,
- const result_type& sigma = 1.0);
- RealType& mean() const;
- RealType& sigma() const;
- void reset();
- template<class UniformRandomNumberGenerator>
- result_type operator()(UniformRandomNumberGenerator& urng);
-};
-</pre>
-
- <h3>Description</h3>
-
- <p>Instantiations of class template <code>lognormal_distribution</code>
- model a random distribution.
- Such a distribution produces random numbers with p(x) = 1/(x * normal_sigma
- * sqrt(2*pi)) * exp( -(log(x)-normal_mean)<sup>2</sup> /
- (2*normal_sigma<sup>2</sup>) ) for x > 0, where normal_mean =
- log(mean<sup>2</sup>/sqrt(sigma<sup>2</sup> + mean<sup>2</sup>)) and
- normal_sigma = sqrt(log(1 + sigma<sup>2</sup>/mean<sup>2</sup>)).
- Each invocation of the UniformRandomNumberGenerator shall result in a
- floating-point value in the range [0,1). </p>
-
- <h3>Members</h3>
- <pre>
-lognormal_distribution(const result_type& mean,
- const result_type& sigma)
-</pre>
-
- <p><strong>Effects:</strong> Constructs a
- <code>lognormal_distribution</code> functor. <code>mean</code> and
- <code>sigma</code> are the mean and standard deviation of the lognormal
- distribution.</p>
-
- <h2><a name="uniform_on_sphere" id="uniform_on_sphere">Class template
- <code>uniform_on_sphere</code></a></h2>
-
- <h3>Synopsis</h3>
- <pre>
-#include <<a href=
-"../../boost/random/uniform_on_sphere.hpp">boost/random/uniform_on_sphere.hpp</a>>
-
-template<class RealType = double,
- class Cont = std::vector<RealType> >
-class uniform_on_sphere
-{
-public:
- typedef RealType input_type;
- typedef Cont result_type;
- explicit uniform_on_sphere(int dim = 2);
- void reset();
- template<class UniformRandomNumberGenerator>
- const result_type & operator()(UniformRandomNumberGenerator& urng);
-};
-</pre>
-
- <h3>Description</h3>
-
- <p>Instantiations of class template <code>uniform_on_sphere</code> model a
- random distribution. Such a
- distribution produces random numbers uniformly distributed on the unit
- sphere of arbitrary dimension <code>dim</code>. The <code>Cont</code>
- template parameter must be a STL-like container type with
- <code>begin</code> and <code>end</code> operations returning non-const
- ForwardIterators of type <code>Cont::iterator</code>.
- Each invocation of the UniformRandomNumberGenerator shall result in a
- floating-point value in the range [0,1). </p>
-
- <h3>Members</h3>
- <pre>
-explicit uniform_on_sphere(int dim = 2)
-</pre>
-
- <p><strong>Effects:</strong> Constructs a <code>uniform_on_sphere</code>
- functor. <code>dim</code> is the dimension of the sphere.</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
- 05
- December, 2006</p>
-
- <p><i>Copyright © 2000-2007 <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 LICENSE_1_0.txt or
- copy at <a href=
- "http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt>)</i></p>
-</body>
-</html>

Deleted: trunk/libs/random/random-generators.html
==============================================================================
--- trunk/libs/random/random-generators.html 2010-03-04 23:59:16 EST (Thu, 04 Mar 2010)
+++ (empty file)
@@ -1,1244 +0,0 @@
-<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
-
-<html>
-<head>
- <meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
-
- <title>Boost Random Number Library Generators</title>
-</head>
-
-<body bgcolor="#FFFFFF" text="#000000">
- <h1>Random Number Library Generators</h1>
-
- <ul>
- <li>Introduction</li>
-
- <li>Synopsis</li>
-
- <li><a href="#const_mod">Class template
- <code>random::const_mod</code></a></li>
-
- <li><a href="#linear_congruential">Class template
- <code>random::linear_congruential</code></a></li>
-
- <li>Class rand48</li>
-
- <li><a href="#additive_combine">Class template
- <code>random::additive_combined</code></a></li>
-
- <li><a href="#shuffle_output">Class template
- <code>random::shuffle_output</code></a></li>
-
- <li><a href="#inversive_congruential">Class template
- <code>random::inversive_congruential</code></a></li>
-
- <li><a href="#mersenne_twister">Class template
- <code>random::mersenne_twister</code></a></li>
-
- <li><a href="#lagged_fibonacci_01">Class template
- <code>random::lagged_fibonacci_01</code></a></li>
-
- <li>Performance</li>
- </ul>
-
- <h2><a name="intro" id="intro">Introduction</a></h2>
-
- <p>This library provides several pseudo-random number generators. The
- quality of a pseudo-random number generator crucially depends on both the
- algorithm and its parameters. This library implements the algorithms as
- class templates with template value parameters, hidden in namespace
- <code>boost::random</code>. Any particular choice of parameters is
- represented as the appropriately specializing <code>typedef</code> in
- namespace <code>boost</code>.</p>
-
- <p>Pseudo-random number generators should not be constructed (initialized)
- frequently during program execution, for two reasons. First, initialization
- requires full initialization of the internal state of the generator. Thus,
- generators with a lot of internal state (see below) are costly to
- initialize. Second, initialization always requires some value used as a
- "seed" for the generated sequence. It is usually difficult to obtain
- several good seed values. For example, one method to obtain a seed is to
- determine the current time at the highest resolution available, e.g.
- microseconds or nanoseconds. When the pseudo-random number generator is
- initialized again with the then-current time as the seed, it is likely that
- this is at a near-constant (non-random) distance from the time given as the
- seed for first initialization. The distance could even be zero if the
- resolution of the clock is low, thus the generator re-iterates the same
- sequence of random numbers. For some applications, this is
- inappropriate.</p>
-
- <p>Note that all pseudo-random number generators described below are
- CopyConstructible and Assignable. Copying or assigning a generator will
- copy all its internal state, so the original and the copy will generate the
- identical sequence of random numbers. Often, such behavior is not wanted.
- In particular, beware of the algorithms from the standard library such as
- std::generate. They take a functor argument by value, thereby invoking the
- copy constructor when called.</p>
-
- <p>The following table gives an overview of some characteristics of the
- generators. The cycle length is a rough estimate of the quality of the
- generator; the approximate relative speed is a performance measure, higher
- numbers mean faster random number generation.</p>
-
- <table border="1" summary="">
- <tr>
- <th>generator</th>
-
- <th>length of cycle</th>
-
- <th>approx. memory requirements</th>
-
- <th>approx. relative speed</th>
-
- <th>comment</th>
- </tr>
-
- <tr>
- <td>minstd_rand</td>
-
- <td>2<sup>31</sup>-2</td>
-
- <td><code>sizeof(int32_t)</code></td>
-
- <td>40</td>
-
- <td>-</td>
- </tr>
-
- <tr>
- <td>rand48</td>
-
- <td>2<sup>48</sup>-1</td>
-
- <td><code>sizeof(uint64_t)</code></td>
-
- <td>80</td>
-
- <td>-</td>
- </tr>
-
- <tr>
- <td><code>lrand48</code> (C library)</td>
-
- <td>2<sup>48</sup>-1</td>
-
- <td>-</td>
-
- <td>20</td>
-
- <td>global state</td>
- </tr>
-
- <tr>
- <td>ecuyer1988</td>
-
- <td>approx. 2<sup>61</sup></td>
-
- <td><code>2*sizeof(int32_t)</code></td>
-
- <td>20</td>
-
- <td>-</td>
- </tr>
-
- <tr>
- <td><code>kreutzer1986</code></td>
-
- <td>?</td>
-
- <td><code>1368*sizeof(uint32_t)</code></td>
-
- <td>60</td>
-
- <td>-</td>
- </tr>
-
- <tr>
- <td><code>hellekalek1995</code></td>
-
- <td>2<sup>31</sup>-1</td>
-
- <td><code>sizeof(int32_t)</code></td>
-
- <td>3</td>
-
- <td>good uniform distribution in several dimensions</td>
- </tr>
-
- <tr>
- <td><code>mt11213b</code></td>
-
- <td>2<sup>11213</sup>-1</td>
-
- <td><code>352*sizeof(uint32_t)</code></td>
-
- <td>100</td>
-
- <td>good uniform distribution in up to 350 dimensions</td>
- </tr>
-
- <tr>
- <td><code>mt19937</code></td>
-
- <td>2<sup>19937</sup>-1</td>
-
- <td><code>625*sizeof(uint32_t)</code></td>
-
- <td>100</td>
-
- <td>good uniform distribution in up to 623 dimensions</td>
- </tr>
-
- <tr>
- <td><code><a href=
- "#lagged_fibonacci_spec">lagged_fibonacci607</a></code></td>
-
- <td>approx. 2<sup>32000</sup></td>
-
- <td><code>607*sizeof(double)</code></td>
-
- <td>150</td>
-
- <td>-</td>
- </tr>
-
- <tr>
- <td><code><a href=
- "#lagged_fibonacci_spec">lagged_fibonacci1279</a></code></td>
-
- <td>approx. 2<sup>67000</sup></td>
-
- <td><code>1279*sizeof(double)</code></td>
-
- <td>150</td>
-
- <td>-</td>
- </tr>
-
- <tr>
- <td><code><a href=
- "#lagged_fibonacci_spec">lagged_fibonacci2281</a></code></td>
-
- <td>approx. 2<sup>120000</sup></td>
-
- <td><code>2281*sizeof(double)</code></td>
-
- <td>150</td>
-
- <td>-</td>
- </tr>
-
- <tr>
- <td><code><a href=
- "#lagged_fibonacci_spec">lagged_fibonacci3217</a></code></td>
-
- <td>approx. 2<sup>170000</sup></td>
-
- <td><code>3217*sizeof(double)</code></td>
-
- <td>150</td>
-
- <td>-</td>
- </tr>
-
- <tr>
- <td><code><a href=
- "#lagged_fibonacci_spec">lagged_fibonacci4423</a></code></td>
-
- <td>approx. 2<sup>230000</sup></td>
-
- <td><code>4423*sizeof(double)</code></td>
-
- <td>150</td>
-
- <td>-</td>
- </tr>
-
- <tr>
- <td><code><a href=
- "#lagged_fibonacci_spec">lagged_fibonacci9689</a></code></td>
-
- <td>approx. 2<sup>510000</sup></td>
-
- <td><code>9689*sizeof(double)</code></td>
-
- <td>150</td>
-
- <td>-</td>
- </tr>
-
- <tr>
- <td><code><a href=
- "#lagged_fibonacci_spec">lagged_fibonacci19937</a></code></td>
-
- <td>approx. 2<sup>1050000</sup></td>
-
- <td><code>19937*sizeof(double)</code></td>
-
- <td>150</td>
-
- <td>-</td>
- </tr>
-
- <tr>
- <td><code><a href=
- "#lagged_fibonacci_spec">lagged_fibonacci23209</a></code></td>
-
- <td>approx. 2<sup>1200000</sup></td>
-
- <td><code>23209*sizeof(double)</code></td>
-
- <td>140</td>
-
- <td>-</td>
- </tr>
-
- <tr>
- <td><code><a href=
- "#lagged_fibonacci_spec">lagged_fibonacci44497</a></code></td>
-
- <td>approx. 2<sup>2300000</sup></td>
-
- <td><code>44497*sizeof(double)</code></td>
-
- <td>60</td>
-
- <td>-</td>
- </tr>
- </table>
-
- <p>As observable from the table, there is generally a
- quality/performance/memory trade-off to be decided upon when choosing a
- random-number generator. The multitude of generators provided in this
- library allows the application programmer to optimize the trade-off with
- regard to his application domain. Additionally, employing several
- fundamentally different random number generators for a given application of
- Monte Carlo simulation will improve the confidence in the results.</p>
-
- <p>If the names of the generators don't ring any bell and you have no idea
- which generator to use, it is reasonable to employ <code>mt19937</code> for
- a start: It is fast and has acceptable quality.</p>
-
- <p><em>Note:</em> These random number generators are not intended for use
- in applications where non-deterministic random numbers are required. See
- nondet_random.html for a choice of
- (hopefully) non-deterministic random number generators.</p>
-
- <p>In this description, I have refrained from documenting those members in
- detail which are already defined in the <a href=
- "random-concepts.html">concept documentation</a>.</p>
-
- <h2><a name="synopsis" id="synopsis">Synopsis of the generators</a>
- available from header <code><boost/random.hpp></code></h2>
- <pre>
-namespace boost {
- namespace random {
- template<class IntType, IntType m>
- class const_mod;
- template<class IntType, IntType a, IntType c, IntType m, IntType val>
- class linear_congruential;
- }
- class rand48;
- typedef random::linear_congruential< /* ... */ > minstd_rand0;
- typedef random::linear_congruential< /* ... */ > minstd_rand;
-
- namespace random {
- template<class DataType, int w, int n, int m, int r, DataType a, int u,
- int s, DataType b, int t, DataType c, int l, IntType val>
- class mersenne_twister;
- }
- typedef random::mersenne_twister< /* ... */ > mt11213b;
- typedef random::mersenne_twister< /* ... */ > mt19937;
-
- namespace random {
- template<class FloatType, int w, unsigned int p, unsigned int q>
- class lagged_fibonacci_01;
- }
- typedef random::lagged_fibonacci_01< /* ... */ > lagged_fibonacci607;
- typedef random::lagged_fibonacci_01< /* ... */ > lagged_fibonacci1279;
- typedef random::lagged_fibonacci_01< /* ... */ > lagged_fibonacci2281;
- typedef random::lagged_fibonacci_01< /* ... */ > lagged_fibonacci3217;
- typedef random::lagged_fibonacci_01< /* ... */ > lagged_fibonacci4423;
- typedef random::lagged_fibonacci_01< /* ... */ > lagged_fibonacci9689;
- typedef random::lagged_fibonacci_01< /* ... */ > lagged_fibonacci19937;
- typedef random::lagged_fibonacci_01< /* ... */ > lagged_fibonacci23209;
- typedef random::lagged_fibonacci_01< /* ... */ > lagged_fibonacci44497;
-} // namespace boost
-</pre>
-
- <h2><a name="const_mod" id="const_mod">Class template
- <code>random::const_mod</code></a></h2>
-
- <h3>Synopsis</h3>
- <pre>
-template<class IntType, IntType m>
-class random::const_mod
-{
-public:
- template<IntType c>
- static IntType add(IntType x);
-
- template<IntType a>
- static IntType mult(IntType x);
-
- template<IntType a, IntType c>
- static IntType mult_add(IntType x);
-
- static IntType invert(IntType x);
-private:
- const_mod(); // don't instantiate
-};
-</pre>
-
- <h3>Description</h3>
-
- <p>Class template <code>const_mod</code> provides functions performing
- modular arithmetic, carefully avoiding overflows. All member functions are
- static; there shall be no objects of type
- <code>const_mod<></code>.</p>
-
- <p>The template parameter <code>IntType</code> shall denote an integral
- type, <code>m</code> is the modulus.</p>
-
- <p><em>Note:</em> For modulo multiplications with large m, a trick allows
- fast computation under certain conditions, see</p>
-
- <blockquote>
- "A more portable FORTRAN random number generator", Linus Schrage, ACM
- Transactions on Mathematical Software, Vol. 5, No. 2, June 1979, pp.
- 132-138
- </blockquote>
-
- <h3>Member functions</h3>
- <pre>
-template<IntType c> static IntType add(IntType x)
-</pre>
-
- <p><strong>Returns:</strong> (x+c) mod m</p>
- <pre>
-template<IntType a> static IntType mult(IntType x)
-</pre>
-
- <p><strong>Returns:</strong> (a*x) mod m</p>
- <pre>
-template<IntType a, IntType c> static IntType
-mult_add(IntType x)
-</pre>
-
- <p><strong>Returns:</strong> (a*x+c) mod m</p>
- <pre>
-static IntType invert(IntType x)
-</pre>
-
- <p><strong>Returns:</strong> i so that (a*i) mod m == 1<br>
- <strong>Precondition:</strong> m is prime</p>
-
- <h2><a name="linear_congruential" id="linear_congruential">Class template
- <code>random::linear_congruential</code></a></h2>
-
- <h3>Synopsis</h3>
- <pre>
-#include <<a href=
-"../../boost/random/linear_congruential.hpp">boost/random/linear_congruential.hpp</a>>
-
-template<class IntType, IntType a, IntType c, IntType m, IntType val>
-class linear_congruential
-{
-public:
- typedef IntType result_type;
- static const IntType multiplier = a;
- static const IntType increment = c;
- static const IntType modulus = m;
- static const bool has_fixed_range = true;
- static const result_type min_value;
- static const result_type max_value;
- explicit linear_congruential_fixed(IntType x0 = 1);
- // compiler-generated copy constructor and assignment operator are fine
- void seed(IntType x0);
- IntType operator()();
-};
-
-typedef random::linear_congruential<long, 16807L, 0, 2147483647L,
- 1043618065L> minstd_rand0;
-typedef random::linear_congruential<long, 48271L, 0, 2147483647L,
- 399268537L> minstd_rand;
-</pre>
-
- <h3>Description</h3>
-
- <p>Instantiations of class template <code>linear_congruential</code> model
- a <a href="random-concepts.html#pseudo-rng">pseudo-random number
- generator</a>. Linear congruential pseudo-random number generators are
- described in:</p>
-
- <blockquote>
- "Mathematical methods in large-scale computing units", D. H. Lehmer,
- Proc. 2nd Symposium on Large-Scale Digital Calculating Machines, Harvard
- University Press, 1951, pp. 141-146
- </blockquote>Let x(n) denote the sequence of numbers returned by some
- pseudo-random number generator. Then for the linear congruential generator,
- x(n+1) := (a * x(n) + c) mod m. Parameters for the generator are x(0), a,
- c, m. The template parameter <code>IntType</code> shall denote an integral
- type. It must be large enough to hold values a, c, and m. The template
- parameters a and c must be smaller than m.
-
- <p><em>Note:</em> The quality of the generator crucially depends on the
- choice of the parameters. User code should use one of the sensibly
- parameterized generators such as <code>minstd_rand</code> instead.<br>
- For each choice of the parameters a, c, m, some distinct type is defined,
- so that the <code>static</code> members do not interfere with regard to the
- one definition rule.</p>
-
- <h3>Members</h3>
- <pre>
-explicit linear_congruential(IntType x0 = 1)
-</pre>
-
- <p><strong>Effects:</strong> Constructs a <code>linear_congruential</code>
- generator, seeding it with <code>x0</code>.</p>
-
- <pre>
-void seed(IntType x0)
-</pre>
-
-
- <p><strong>Effects:</strong> If <code>c</code> mod <code>m</code> is zero
- and <code>x0</code> mod <code>m</code> is zero, changes the current value of
- the generator to 1. Otherwise, changes it to <code>x0</code> mod
- <code>m</code>. If <code>c</code> is zero, distinct seeds in the range
- [1,m) will leave the generator in distinct states. If <code>c</code>
- is not zero, the range is [0,m).
- </p>
-
- <h3><a name="minstd_rand" id="minstd_rand">Specializations</a></h3>
-
- <p>The specialization <code>minstd_rand0</code> was originally suggested
- in</p>
-
- <blockquote>
- A pseudo-random number generator for the System/360, P.A. Lewis, A.S.
- Goodman, J.M. Miller, IBM Systems Journal, Vol. 8, No. 2, 1969, pp.
- 136-146
- </blockquote>It is examined more closely together with
- <code>minstd_rand</code> in
-
- <blockquote>
- "Random Number Generators: Good ones are hard to find", Stephen K. Park
- and Keith W. Miller, Communications of the ACM, Vol. 31, No. 10, October
- 1988, pp. 1192-1201
- </blockquote>
-
- <h2><a name="rand48" id="rand48">Class <code>rand48</code></a></h2>
-
- <h3>Synopsis</h3>
- <pre>
-#include <<a href=
-"../../boost/random/linear_congruential.hpp">boost/random/linear_congruential.hpp</a>>
-
-class rand48
-{
-public:
- typedef int32_t result_type;
- static const bool has_fixed_range = true;
- static const int32_t min_value = 0;
- static const int32_t max_value = 0x7fffffff;
-
- explicit rand48(int32_t x0 = 1);
- explicit rand48(uint64_t x0);
- // compiler-generated copy ctor and assignment operator are fine
- void seed(int32_t x0);
- void seed(uint64_t x0);
- int32_t operator()();
-};
-</pre>
-
- <h3>Description</h3>
-
- <p>Class <code>rand48</code> models a <a href=
- "random-concepts.html#pseudo-rng">pseudo-random number generator</a>. It
- uses the linear congruential algorithm with the parameters a = 0x5DEECE66D,
- c = 0xB, m = 2**48. It delivers identical results to the
- <code>lrand48()</code> function available on some systems (assuming
- <code>lcong48</code> has not been called).</p>
-
- <p>It is only available on systems where <code>uint64_t</code> is provided
- as an integral type, so that for example static in-class constants and/or
- enum definitions with large <code>uint64_t</code> numbers work.</p>
-
- <h3>Constructors</h3>
- <pre>
-rand48(int32_t x0)
-</pre>
-
- <p><strong>Effects:</strong> Constructs a <code>rand48</code> generator
- with x(0) := (<code>x0</code> << 16) | 0x330e.</p>
- <pre>
-rand48(uint64_t x0)
-</pre>
-
- <p><strong>Effects:</strong> Constructs a <code>rand48</code> generator
- with x(0) := <code>x0</code>.</p>
-
- <h3>Seeding</h3>
- <pre>
-void seed(int32_t x0)
-</pre>
-
- <p><strong>Effects:</strong> Changes the current value x(n) of the
- generator to (<code>x0</code> << 16) | 0x330e.</p>
- <pre>
-void seed(uint64_t x0)
-</pre>
-
- <p><strong>Effects:</strong> Changes the current value x(n) of the
- generator to <code>x0</code>.</p>
-
- <h2><a name="additive_combine" id="additive_combine">Class template
- <code>random::additive_combine</code></a></h2>
-
- <h3>Synopsis</h3>
- <pre>
-#include <<a href=
-"../../boost/random/additive_combine.hpp">boost/random/additive_combine.hpp</a>>
-
-template<class MLCG1, class MLCG2, typename MLCG1::result_type val>
-class random::additive_combine
-{
-public:
- typedef MLCG1 first_base;
- typedef MLCG2 second_base;
- typedef typename MLCG1::result_type result_type;
- static const bool has_fixed_range = true;
- static const result_type min_value = 1;
- static const result_type max_value = MLCG1::max_value-1;
- additive_combine();
- additive_combine(typename MLCG1::result_type seed);
- additive_combine(typename MLCG1::result_type seed1,
- typename MLCG2::result_type seed2);
- void seed();
- void seed(typename MLCG1::result_type seed);
- void seed(typename MLCG1::result_type seed1,
- typename MLCG2::result_type seed2);
- result_type operator()();
- bool validation(result_type x) const;
-};
-
-typedef random::additive_combine<
- random::linear_congruential<int32_t, 40014, 0, 2147483563, 0>,
- random::linear_congruential<int32_t, 40692, 0, 2147483399, 0>,
- /* unknown */ 0> ecuyer1988;
-
-</pre>
-
- <h3>Description</h3>
-
- <p>Instatiations of class template <code>additive_combine</code> model a
- <a href="random-concepts.html#pseudo-rng">pseudo-random number
- generator</a>. It combines two multiplicative linear congruential number
- generators, i.e. those with c = 0. It is described in</p>
-
- <blockquote>
- "Efficient and Portable Combined Random Number Generators", Pierre
- L'Ecuyer, Communications of the ACM, Vol. 31, No. 6, June 1988, pp.
- 742-749, 774
- </blockquote>The template parameters <code>MLCG1</code> and
- <code>MLCG2</code> shall denote two different linear congruential number
- generators, each with c = 0. Each invocation returns a random number X(n)
- := (MLCG1(n) - MLCG2(n)) mod (m1 - 1), where m1 denotes the modulus of
- <code>MLCG1</code>.
-
- <p>The template parameter <code>val</code> is the validation value checked
- by <code>validation</code>.</p>
-
- <h3>Members</h3>
- <pre>
-additive_combine()
-</pre>
-
- <p><strong>Effects:</strong> Constructs an <code>additive_combine</code>
- generator using the default constructors of the two base generators.</p>
-
- <pre>
-additive_combine(typename MLCG1::result_type seed)
-</pre>
-
- <p><strong>Effects:</strong> Constructs an <code>additive_combine</code>
- generator, using <code>seed</code> as the constructor argument for
- both base generators.</p>
-
- <pre>
-additive_combine(typename MLCG1::result_type seed1,
- typename MLCG2::result_type seed2)
-</pre>
-
- <p><strong>Effects:</strong> Constructs an <code>additive_combine</code>
- generator, using <code>seed1</code> and <code>seed2</code> as the
- constructor argument to the first and second base generator,
- respectively.</p>
-
- <pre>
-void seed()
-</pre>
-
- <p><strong>Effects:</strong> Seeds an <code>additive_combine</code>
- generator using the default seeds of the two base generators.</p>
-
- <pre>
-void seed(typename MLCG1::result_type seed)
-</pre>
-
- <p><strong>Effects:</strong> Seeds an <code>additive_combine</code>
- generator, using <code>seed</code> as the seed for both base
- generators.</p>
-
- <pre>
-void seed(typename MLCG1::result_type seed1,
- typename MLCG2::result_type seed2)
-</pre>
-
- <p><strong>Effects:</strong> Seeds an <code>additive_combine</code>
- generator, using <code>seed1</code> and <code>seed2</code> as the
- seeds to the first and second base generator, respectively.</p>
-
- <h3><a name="ecuyer1988" id="ecuyer1988">Specialization</a></h3>
-
- <p>The specialization <code>ecuyer1988</code> was suggested in the above
- paper.</p>
-
- <h2><a name="shuffle_output" id="shuffle_output">Class template
- <code>random::shuffle_output</code></a></h2>
-
- <h3>Synopsis</h3>
- <pre>
-#include <<a href=
-"../../boost/random/shuffle_output.hpp">boost/random/shuffle_output.hpp</a>>
-
-template<class UniformRandomNumberGenerator, int k,
- typename UniformRandomNumberGenerator::result_type val = 0>
-class random::shuffle_output
-{
-public:
- typedef UniformRandomNumberGenerator base_type;
- typedef typename base_type::result_type result_type;
- static const bool has_fixed_range = false;
-
- shuffle_output();
- template<class T> explicit shuffle_output(T seed);
- explicit shuffle_output(const base_type & rng);
- template<class T> void seed(T s);
-
- result_type operator()();
- result_type min() const;
- result_type max() const;
- bool validation(result_type) const;
-};
-</pre>
-
- <h3>Description</h3>
-
- <p>Instatiations of class template <code>shuffle_output</code> model a
- <a href="random-concepts.html#pseudo-rng">pseudo-random number
- generator</a>. It mixes the output of some (usually linear congruential)
- uniform random number generator to get better statistical properties.
- According to Donald E. Knuth, "The Art of Computer Programming, Vol. 2",
- the algorithm is described in</p>
-
- <blockquote>
- "Improving a poor random number generator", Carter Bays and S.D. Durham,
- ACM Transactions on Mathematical Software, Vol. 2, 1979, pp. 59-64.
- </blockquote>The output of the base generator is buffered in an array of
- length k. Every output X(n) has a second role: It gives an index into the
- array where X(n+1) will be retrieved. Used array elements are replaced with
- fresh output from the base generator.
-
- <p>Template parameters are the base generator and the array length k, which
- should be around 100. The template parameter <code>val</code> is the
- validation value checked by <code>validation</code>.</p>
-
- <h3>Members</h3>
- <pre>
-shuffle_output()
-</pre>
-
- <p><strong>Effects:</strong> Constructs a <code>shuffle_output</code>
- generator by invoking the default constructor of the base generator.</p>
-
- <p><strong>Complexity:</strong> Exactly k+1 invocations of the base
- generator.</p>
- <pre>
-template<class T> explicit shuffle_output(T seed)
-</pre>
-
- <p><strong>Effects:</strong> Constructs a <code>shuffle_output</code>
- generator by invoking the one-argument constructor of the base generator
- with the parameter <code>seed</code>.</p>
-
- <p><strong>Complexity:</strong> Exactly k+1 invocations of the base
- generator.</p>
- <pre>
-explicit shuffle_output(const base_type & rng)
-</pre>
-
- <p><strong>Precondition:</strong> The template argument
- <code>UniformRandomNumberGenerator</code> shall denote a CopyConstructible
- type.</p>
-
- <p><strong>Effects:</strong> Constructs a <code>shuffle_output</code>
- generator by using a copy of the provided generator.</p>
-
- <p><strong>Complexity:</strong> Exactly k+1 invocations of the base
- generator.</p>
- <pre>
-template<class T> void seed(T s)
-</pre>
-
- <p><strong>Effects:</strong> Invokes the one-argument <code>seed</code>
- method of the base generator with the parameter <code>seed</code> and
- re-initializes the internal buffer array.</p>
-
- <p><strong>Complexity:</strong> Exactly k+1 invocations of the base
- generator.</p>
-
- <h3><a name="kreutzer1986" id="kreutzer1986">Specializations</a></h3>
-
- <p>According to Harry Erwin (private e-mail), the specialization
- <code>kreutzer1986</code> was suggested in:</p>
-
- <blockquote>
- "System Simulation: programming Styles and Languages (International
- Computer Science Series)", Wolfgang Kreutzer, Addison-Wesley, December
- 1986.
- </blockquote>
-
- <h2><a name="inversive_congruential" id="inversive_congruential">Class
- template <code>random::inversive_congruential</code></a></h2>
-
- <h3>Synopsis</h3>
- <pre>
-#include <<a href=
-"../../boost/random/inversive_congruential.hpp">boost/random/inversive_congruential.hpp</a>>
-
-template<class IntType, IntType a, IntType b, IntType p, IntType val>
-class random::inversive_congruential
-{
-public:
- typedef IntType result_type;
- static const bool has_fixed_range = true;
- static const result_type min_value = (b == 0 ? 1 : 0);
- static const result_type max_value = p-1;
- static const result_type multiplier = a;
- static const result_type increment = b;
- static const result_type modulus = p;
- explicit inversive_congruential(IntType y0 = 1);
- void seed(IntType y0);
- IntType operator()();
-};
-
-typedef random::inversive_congruential<int32_t, 9102, 2147483647-36884165, 2147483647, 0> hellekalek1995;
-</pre>
-
- <h3>Description</h3>
-
- <p>Instantiations of class template <code>inversive_congruential</code>
- model a <a href="random-concepts.html#pseudo-rng">pseudo-random number
- generator</a>. It uses the inversive congruential algorithm (ICG) described
- in</p>
-
- <blockquote>
- "Inversive pseudorandom number generators: concepts, results and links",
- Peter Hellekalek, In: "Proceedings of the 1995 Winter Simulation
- Conference", C. Alexopoulos, K. Kang, W.R. Lilegdon, and D. Goldsman
- (editors), 1995, pp. 255-262. <a href=
- "ftp://random.mat.sbg.ac.at/pub/data/wsc95.ps">ftp://random.mat.sbg.ac.at/pub/data/wsc95.ps>
- </blockquote>The output sequence is defined by x(n+1) = (a*inv(x(n)) - b)
- (mod p), where x(0), a, b, and the prime number p are parameters of the
- generator. The expression inv(k) denotes the multiplicative inverse of k in
- the field of integer numbers modulo p, with inv(0) := 0.
-
- <p>The template parameter <code>IntType</code> shall denote a signed
- integral type large enough to hold p; a, b, and p are the parameters of the
- generators. The template parameter val is the validation value checked by
- validation.</p>
-
- <p><em>Note:</em> The implementation currently uses the Euclidian Algorithm
- to compute the multiplicative inverse. Therefore, the inversive generators
- are about 10-20 times slower than the others (see section"<a href=
- "#performance">performance</a>"). However, the paper talks of only 3x
- slowdown, so the Euclidian Algorithm is probably not optimal for
- calculating the multiplicative inverse.</p>
-
- <h3>Members</h3>
- <pre>
-inversive_congruential(IntType y0 = 1)
-</pre>
-
- <p><strong>Effects:</strong> Constructs an
- <code>inversive_congruential</code> generator with <code>y0</code> as the
- initial state.</p>
- <pre>
-void seed(IntType y0)
-</pre>
-
- <p><strong>Effects:</strong> Changes the current state to
- <code>y0</code>.</p>
-
- <h3><a name="hellekalek1995" id="hellekalek1995">Specialization</a></h3>
-
- <p>The specialization <code>hellekalek1995</code> was suggested in the
- above paper.</p>
-
- <h2><a name="mersenne_twister" id="mersenne_twister">Class template
- <code>random::mersenne_twister</code></a></h2>
-
- <h3>Synopsis</h3>
- <pre>
-#include <<a href=
-"../../boost/random/mersenne_twister.hpp">boost/random/mersenne_twister.hpp</a>>
-
-template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
- int s, UIntType b, int t, UIntType c, int l, UIntType val>
-class random::mersenne_twister
-{
-public:
- typedef UIntType result_type;
- static const bool has_fixed_range = false;
- mersenne_twister();
- explicit mersenne_twister(UIntType value);
- template<class Generator> explicit mersenne_twister(Generator & gen);
- // compiler-generated copy ctor and assignment operator are fine
- void seed();
- void seed(UIntType value);
- template<class Generator> void seed(Generator & gen);
- result_type operator()();
- bool validation(result_type) const;
-};
-
-typedef mersenne_twister<uint32_t,351,175,19,0xccab8ee7,11,7,0x31b6ab00,15,0xffe50000,17, /* unknown */ 0> mt11213b;
-typedef mersenne_twister<uint32_t,624,397,31,0x9908b0df,11,7,0x9d2c5680,15,0xefc60000,18, 3346425566U> mt19937;
-</pre>
-
- <h3>Description</h3>
-
- <p>Instantiations of class template <code>mersenne_twister</code> model a
- <a href="random-concepts.html#pseudo-rng">pseudo-random number
- generator</a>. It uses the algorithm described in</p>
-
- <blockquote>
- "Mersenne Twister: A 623-dimensionally equidistributed uniform
- pseudo-random number generator", Makoto Matsumoto and Takuji Nishimura,
- ACM Transactions on Modeling and Computer Simulation: Special Issue on
- Uniform Random Number Generation, Vol. 8, No. 1, January 1998, pp. 3-30.
- 
- </blockquote><em>Note:</em> The boost variant has been implemented from
- scratch and does not derive from or use mt19937.c provided on the above WWW
- site. However, it was verified that both produce identical output.<br>
- The seeding from an integer was changed in April 2005 to address a <a href=
- "http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/emt19937ar.html">weakness</a>.<br>
-
- The quality of the generator crucially depends on the choice of the
- parameters. User code should employ one of the sensibly parameterized
- generators such as <code>mt19937</code> instead.<br>
- The generator requires considerable amounts of memory for the storage of
- its state array. For example, <code>mt11213b</code> requires about 1408
- bytes and <code>mt19937</code> requires about 2496 bytes.
-
- <h3>Constructors</h3>
- <pre>
-mersenne_twister()
-</pre>
-
- <p><strong>Effects:</strong> Constructs a <code>mersenne_twister</code> and
- calls <code>seed()</code>.</p>
- <pre>
-explicit mersenne_twister(result_type value)
-</pre>
-
- <p><strong>Effects:</strong> Constructs a <code>mersenne_twister</code> and
- calls <code>seed(value)</code>.</p>
- <pre>
-template<class Generator> explicit mersenne_twister(Generator & gen)
-</pre>
-
- <p><strong>Effects:</strong> Constructs a <code>mersenne_twister</code> and
- calls <code>seed(gen)</code>.</p>
-
- <p><em>Note:</em> The copy constructor will always be preferred over the
- templated constructor. mersenne_twister takes special steps to guarantee
- this.</p>
-
- <h3>Seeding</h3>
- <pre>
-void seed()
-</pre>
-
- <p><strong>Effects:</strong> Calls
- <code>seed(result_type(5489))</code>.</p>
- <pre>
-void seed(result_type value)
-</pre>
-
- <p><strong>Effects:</strong> Sets the state x(0) to v mod 2<sup>w</sup>.
- Then, iteratively,<br>
- sets x(i) to (i + 1812433253 * (x(i-1) <em>xor</em> (x(i-1) <em>rshift</em>
- w-2))) mod 2<sup>w</sup> for i = 1 .. n-1. x(n) is the first value to be
- returned by operator().</p>
- <pre>
-template<class Generator> void seed(Generator & gen)
-</pre>
-
- <p><strong>Effects:</strong> Sets the state of this
- <code>mersenne_twister</code> to the values returned by <code>n</code>
- invocations of <code>gen</code>.</p>
-
- <p><strong>Complexity:</strong> Exactly <code>n</code> invocations of
- <code>gen</code>.</p>
-
- <h3><a name="mt11213b" id="mt11213b"></a><a name="mt19937" id=
- "mt19937">Specializations</a></h3>
-
- <p>The specializations <code>mt11213b</code> and <code>mt19937</code> are
- from the paper cited above.</p>
-
- <h2><a name="lagged_fibonacci_01" id="lagged_fibonacci_01">Class template
- <code>random::lagged_fibonacci_01</code></a></h2>
-
- <h3>Synopsis</h3>
- <pre>
-#include <<a href=
-"../../boost/random/lagged_fibonacci.hpp">boost/random/lagged_fibonacci.hpp</a>>
-
-template<class FloatType, int w, unsigned int p, unsigned int q>
-class lagged_fibonacci_01
-{
-public:
- typedef FloatType result_type;
- static const bool has_fixed_range = false;
- static const int word_size = w;
- static const unsigned int long_lag = p;
- static const unsigned int short_lag = q;
- result_type min() const { return 0.0; }
- result_type max() const { return 1.0; }
- lagged_fibonacci_01();
- explicit lagged_fibonacci_01(uint32_t value);
- template<class Generator>
- explicit lagged_fibonacci_01(Generator & gen);
- // compiler-generated copy ctor and assignment operator are fine
- void seed(uint32_t value = 331u);
- template<class Generator> void seed(Generator & gen);
- result_type operator()();
- bool validation(result_type x) const;
-};
-
-typedef random::lagged_fibonacci_01<double, 48, 607, 273> lagged_fibonacci607;
-typedef random::lagged_fibonacci_01<double, 48, 1279, 418> lagged_fibonacci1279;
-typedef random::lagged_fibonacci_01<double, 48, 2281, 1252> lagged_fibonacci2281;
-typedef random::lagged_fibonacci_01<double, 48, 3217, 576> lagged_fibonacci3217;
-typedef random::lagged_fibonacci_01<double, 48, 4423, 2098> lagged_fibonacci4423;
-typedef random::lagged_fibonacci_01<double, 48, 9689, 5502> lagged_fibonacci9689;
-typedef random::lagged_fibonacci_01<double, 48, 19937, 9842> lagged_fibonacci19937;
-typedef random::lagged_fibonacci_01<double, 48, 23209, 13470> lagged_fibonacci23209;
-typedef random::lagged_fibonacci_01<double, 48, 44497, 21034> lagged_fibonacci44497;
-</pre>
-
- <h3>Description</h3>
-
- <p>Instantiations of class template <code>lagged_fibonacci_01</code> model a
- <a href="random-concepts.html#pseudo-rng">pseudo-random number
- generator</a>. It uses a lagged Fibonacci algorithm with two lags p and q,
- evaluated in floating-point arithmetic: x(i) = x(i-p) + x(i-q) (mod 1) with
- p > q. See</p>
-
- <blockquote>
- "Uniform random number generators for supercomputers", Richard Brent,
- Proc. of Fifth Australian Supercomputer Conference, Melbourne, Dec. 1992,
- pp. 704-706.
- </blockquote>
-
- <p><em>Note:</em> The quality of the generator crucially depends on the
- choice of the parameters. User code should employ one of the sensibly
- parameterized generators such as <code>lagged_fibonacci607</code>
- instead.<br>
- The generator requires considerable amounts of memory for the storage of
- its state array. For example, <code>lagged_fibonacci607</code> requires
- about 4856 bytes and <code>lagged_fibonacci44497</code> requires about 350
- KBytes.</p>
-
- <h3>Constructors</h3>
- <pre>
-lagged_fibonacci_01()
-</pre>
-
- <p><strong>Effects:</strong> Constructs a <code>lagged_fibonacci_01</code>
- generator and calls <code>seed()</code>.</p>
- <pre>
-explicit lagged_fibonacci_01(uint32_t value)
-</pre>
-
- <p><strong>Effects:</strong> Constructs a <code>lagged_fibonacci_01</code>
- generator and calls <code>seed(value)</code>.</p>
- <pre>
-template<class Generator> explicit lagged_fibonacci_01(Generator & gen)
-</pre>
-
- <p><strong>Effects:</strong> Constructs a <code>lagged_fibonacci_01</code>
- generator and calls <code>seed(gen)</code>.</p>
-
- <h3>Seeding</h3>
- <pre>
-void seed()
-</pre>
-
- <p><strong>Effects:</strong> Calls <code>seed(331u)</code>.</p>
- <pre>
-void seed(uint32_t value)
-</pre>
-
- <p><strong>Effects:</strong> Constructs a <code>minstd_rand0</code>
- generator with the constructor parameter <code>value</code> and calls
- <code>seed</code> with it. Distinct seeds in the range [1, 2147483647)
- will produce generators with different states. Other seeds will be
- equivalent to some seed within this range. See
- linear_congruential for details.</p>
- <pre>
-template<class Generator> void seed(Generator & gen)
-</pre>
-
- <p><strong>Effects:</strong> Sets the state of this
- <code>lagged_fibonacci_01</code> to the values returned by <code>p</code>
- invocations of <code>uniform_01<gen, FloatType></code>.<br>
- <strong>Complexity:</strong> Exactly <code>p</code> invocations of
- <code>gen</code>.</p>
-
- <h3><a name="lagged_fibonacci_spec" id=
- "lagged_fibonacci_spec"></a>Specializations</h3>
-
- <p>The specializations <code>lagged_fibonacci607</code> ...
- <code>lagged_fibonacci44497</code> (see above) use well tested lags.
- (References will be added later.)</p>
-
- <h2><a name="performance" id="performance">Performance</a></h2>
-
- <p>The test program random_speed.cpp
- measures the execution times of the <a href=
- "../../boost/random.hpp">random.hpp</a> implementation of the above
- algorithms in a tight loop. The performance has been evaluated on a Pentium
- Pro 200 MHz with gcc 2.95.2, Linux 2.2.13, glibc 2.1.2.</p>
-
- <table border="1" summary="">
- <tr>
- <th>class</th>
-
- <th>time per invocation [usec]</th>
- </tr>
-
- <tr>
- <td>rand48</td>
-
- <td>0.096</td>
- </tr>
-
- <tr>
- <td>rand48 run-time configurable</td>
-
- <td>0.697</td>
- </tr>
-
- <tr>
- <td>lrand48 glibc 2.1.2</td>
-
- <td>0.844</td>
- </tr>
-
- <tr>
- <td>minstd_rand</td>
-
- <td>0.174</td>
- </tr>
-
- <tr>
- <td>ecuyer1988</td>
-
- <td>0.445</td>
- </tr>
-
- <tr>
- <td>kreutzer1986</td>
-
- <td>0.249</td>
- </tr>
-
- <tr>
- <td>hellekalek1995 (inversive)</td>
-
- <td>4.895</td>
- </tr>
-
- <tr>
- <td>mt11213b</td>
-
- <td>0.165</td>
- </tr>
-
- <tr>
- <td>mt19937</td>
-
- <td>0.165</td>
- </tr>
-
- <tr>
- <td>mt19937 original</td>
-
- <td>0.185</td>
- </tr>
-
- <tr>
- <td>lagged_fibonacci607</td>
-
- <td>0.111</td>
- </tr>
-
- <tr>
- <td>lagged_fibonacci4423</td>
-
- <td>0.112</td>
- </tr>
-
- <tr>
- <td>lagged_fibonacci19937</td>
-
- <td>0.113</td>
- </tr>
-
- <tr>
- <td>lagged_fibonacci23209</td>
-
- <td>0.122</td>
- </tr>
-
- <tr>
- <td>lagged_fibonacci44497</td>
-
- <td>0.263</td>
- </tr>
- </table>
-
- <p>The measurement error is estimated at +/- 10 nsec.</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
- 05
- December, 2006</p>
-
- <p><i>Copyright © 2000-2005 <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 LICENSE_1_0.txt or
- copy at <a href=
- "http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt>)</i></p>
-</body>
-</html>

Deleted: trunk/libs/random/random-misc.html
==============================================================================
--- trunk/libs/random/random-misc.html 2010-03-04 23:59:16 EST (Thu, 04 Mar 2010)
+++ (empty file)
@@ -1,99 +0,0 @@
-<!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 Generator Library (Miscellaneous)</title>
-</head>
-
-<body bgcolor="#FFFFFF" text="#000000">
- <h1>Random Number Generator Library --- Miscellaneous Decorators</h1>
-
- <ul>
- <li><a href="#random_number_generator">Class template
- <code>random_number_generator</code></a></li>
- </ul>
-
- <h2>Introduction</h2>
-
- <p>These decorator class templates allow adaptation of the random number
- generators and distribution functions to concepts found in the C++ Standard
- Library, in particular the RandomNumberGenerator and the InputIterator
- concepts. The latter adaptation is useful, because the the basic random
- number generators do not implement the InputIterator requirements per se,
- in contrast to the distribution functions.</p>
-
- <h2><a name="synopsis" id="synopsis">Synopsis</a> of miscellaneous
- decorators in header <code><boost/random.hpp></code></h2>
- <pre>
-namespace boost {
- template<class UniformRandomNumberGenerator, class IntType = long>
- class random_number_generator;
-} // namespace boost
-</pre>
-
- <h2><a name="random_number_generator" id="random_number_generator">Class
- template <code>random_number_generator</code></a></h2>
-
- <h3>Synopsis</h3>
- <pre>
-template<class UniformRandomNumberGenerator, class IntType = long>
-class random_number_generator
-{
-public:
- typedef UniformRandomNumberGenerator base_type;
- typedef IntType argument_type;
- typedef IntType result_type;
- random_number_generator(base_type & rng);
- result_type operator()(argument_type n);
-};
-</pre>
-
- <h3>Description</h3>
-
- <p>Instantiations of class template <code>random_number_generator</code>
- model a RandomNumberGenerator (std:25.2.11 [lib.alg.random.shuffle]). On
- each invocation, it returns a uniformly distributed integer in the range
- [0..<code>n</code>).</p>
-
- <p>The template parameter <code>IntType</code> shall denote some
- integer-like value type.</p>
-
- <p><em>Note:</em> I consider it unfortunate that the C++ Standard uses the
- name RandomNumberGenerator for something rather specific.</p>
-
- <h3>Members</h3>
- <pre>
-random_number_generator(base_type & rng)
-</pre>
-
- <p><strong>Effects:</strong> Constructs a
- <code>random_number_generator</code> functor with the given uniform random
- number generator as the underlying source of random numbers.</p>
- <pre>
-result_type operator()(argument_type n)
-</pre>
-
- <p><strong>Returns:</strong> The value of
- <code>uniform_int<base_type>(rng, 0, n-1)()</code>.</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
- 05
- December, 2006</p>
-
- <p><i>Copyright © 2000-2005 <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 LICENSE_1_0.txt or
- copy at <a href=
- "http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt>)</i></p>
-</body>
-</html>

Deleted: trunk/libs/random/random-performance.html
==============================================================================
--- trunk/libs/random/random-performance.html 2010-03-04 23:59:16 EST (Thu, 04 Mar 2010)
+++ (empty file)
@@ -1,338 +0,0 @@
-<!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 Performance</title>
-</head>
-
-<body bgcolor="#FFFFFF" text="#000000">
- <h1>Random Number Library Performance</h1>
-
- <p>For some people, performance of random number generation is an important
- consideration when choosing a random number generator or a particular
- distribution function. This page provides numerous performance tests with
- the wide variety of generators and distributions available in the boost
- library.</p>
-
- <p>The performance has been evaluated on a Pentium Pro 200 MHz with gcc
- 2.95.2, Linux 2.2.13, glibc 2.1.2. The speed is reported in million random
- numbers per second (M rn/sec), generated in a tight loop.</p>
-
- <h2>Basic Generators</h2>
-
- <table border="1" summary="">
- <tr>
- <th>generator</th>
-
- <th>M rn/sec</th>
-
- <th>time per random number [usec]</th>
-
- <th>relative speed compared to fastest [percent]</th>
- </tr>
-
- <tr>
- <td>rand48</td>
-
- <td>5.38</td>
-
- <td>0.183</td>
-
- <td>61%</td>
- </tr>
-
- <tr>
- <td>rand48 run-time configurable</td>
-
- <td>1.48</td>
-
- <td>0.677</td>
-
- <td>17%</td>
- </tr>
-
- <tr>
- <td>lrand48 glibc 2.1.2</td>
-
- <td>1.19</td>
-
- <td>0.843</td>
-
- <td>13%</td>
- </tr>
-
- <tr>
- <td>minstd_rand</td>
-
- <td>2.39</td>
-
- <td>0.318</td>
-
- <td>35%</td>
- </tr>
-
- <tr>
- <td>ecuyer1988</td>
-
- <td>1.12</td>
-
- <td>0.892</td>
-
- <td>13%</td>
- </tr>
-
- <tr>
- <td>kreutzer1986</td>
-
- <td>3.87</td>
-
- <td>0.258</td>
-
- <td>43%</td>
- </tr>
-
- <tr>
- <td>hellekalek1995 (inversive)</td>
-
- <td>0.20</td>
-
- <td>5.12</td>
-
- <td>2%</td>
- </tr>
-
- <tr>
- <td>mt11213b</td>
-
- <td>6.07</td>
-
- <td>0.165</td>
-
- <td>68%</td>
- </tr>
-
- <tr>
- <td>mt19937</td>
-
- <td>6.06</td>
-
- <td>0.165</td>
-
- <td>68%</td>
- </tr>
-
- <tr>
- <td>mt19937 original</td>
-
- <td>5.33</td>
-
- <td>0.188</td>
-
- <td>60%</td>
- </tr>
-
- <tr>
- <td>lagged_fibonacci607</td>
-
- <td>8.90</td>
-
- <td>0.112</td>
-
- <td>100%</td>
- </tr>
-
- <tr>
- <td>lagged_fibonacci4423</td>
-
- <td>8.54</td>
-
- <td>0.117</td>
-
- <td>96%</td>
- </tr>
-
- <tr>
- <td>lagged_fibonacci19937</td>
-
- <td>7.49</td>
-
- <td>0.133</td>
-
- <td>84%</td>
- </tr>
-
- <tr>
- <td>lagged_fibonacci23209</td>
-
- <td>6.63</td>
-
- <td>0.151</td>
-
- <td>74%</td>
- </tr>
-
- <tr>
- <td>lagged_fibonacci44497</td>
-
- <td>4.01</td>
-
- <td>0.250</td>
-
- <td>45%</td>
- </tr>
- </table>
-
- <p>Note that the lagged Fibonacci generators produce floating-point
- numbers, whereas all others produce integers.</p>
-
- <h2>Distributions</h2>
-
- <table border="1" summary="">
- <tr>
- <th>[M rn/sec]</th>
-
- <th>minstd_rand</th>
-
- <th>kreutzer1986</th>
-
- <th>mt19937</th>
-
- <th>lagged_fibonacci607</th>
- </tr>
-
- <tr>
- <th>uniform_smallint</th>
-
- <td>1.26</td>
-
- <td>1.55</td>
-
- <td>1.93</td>
-
- <td>-</td>
- </tr>
-
- <tr>
- <th>uniform_01</th>
-
- <td>1.79</td>
-
- <td>1.88</td>
-
- <td>3.03</td>
-
- <td>7.74</td>
- </tr>
-
- <tr>
- <th>uniform_real</th>
-
- <td>1.74</td>
-
- <td>1.56</td>
-
- <td>2.34</td>
-
- <td>6.62</td>
- </tr>
-
- <tr>
- <th>geometric</th>
-
- <td>0.593</td>
-
- <td>0.629</td>
-
- <td>0.753</td>
-
- <td>0.916</td>
- </tr>
-
- <tr>
- <th>triangle</th>
-
- <td>0.97</td>
-
- <td>1.02</td>
-
- <td>1.35</td>
-
- <td>1.31</td>
- </tr>
-
- <tr>
- <th>exponential</th>
-
- <td>0.849</td>
-
- <td>0.828</td>
-
- <td>0.887</td>
-
- <td>1.53</td>
- </tr>
-
- <tr>
- <th>normal (polar method)</th>
-
- <td>0.608</td>
-
- <td>0.626</td>
-
- <td>0.738</td>
-
- <td>0.755</td>
- </tr>
-
- <tr>
- <th>lognormal</th>
-
- <td>0.417</td>
-
- <td>0.442</td>
-
- <td>0.470</td>
-
- <td>0.481</td>
- </tr>
-
- <tr>
- <th>uniform_on_sphere</th>
-
- <td>0.154</td>
-
- <td>0.155</td>
-
- <td>0.174</td>
-
- <td>0.218</td>
- </tr>
- </table>
-
- <p>Note that the lagged Fibonacci generator is at least 2.5 times faster
- than the Mersenne twister when generating uniformly distributed
- floating-point numbers. For more sophisticated distributions, the speed
- improvement is less. Note however that these distributions have not been
- optimized for speed, yet.</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
- 05
- December, 2006</p>
-
- <p><i>Copyright © 2001 <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 LICENSE_1_0.txt or
- copy at <a href=
- "http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt>)</i></p>
-</body>
-</html>

Deleted: trunk/libs/random/random-variate.html
==============================================================================
--- trunk/libs/random/random-variate.html 2010-03-04 23:59:16 EST (Thu, 04 Mar 2010)
+++ (empty file)
@@ -1,164 +0,0 @@
-<!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 Variate Generator</title>
-</head>
-
-<body bgcolor="#FFFFFF" text="#000000">
- <h1>Boost Random Number Library Variate Generator</h1>
-
- <p>A random variate generator is used to join a random number generator
- together with a random number distribution. Boost.Random provides a vast
- choice of generators as well as
- distributions .</p>
-
- <h2><a name="variate_generator" id="variate_generator">Class template
- <code>variate_generator</code></a></h2>
-
- <h3>Synopsis</h3>
- <pre>
-#include <<a href=
-"../../boost/random/variate_generator.hpp">boost/random/variate_generator.hpp</a>>
-
-template<class Engine, class Distribution>
-class variate_generator
-{
-public:
- typedef Engine engine_type;
- typedef Distribution distribution_type;
- typedef typename Distribution::result_type result_type;
-
- variate_generator(Engine e, Distribution d);
-
- result_type operator()();
- template<class T>
- result_type operator()(T value);
-
- engine_value_type& engine();
- const engine_value_type& engine() const;
-
- result_type min() const;
- result_type max() const;
-};
-</pre>
-
- <h3>Description</h3>
-
- <p>Instantations of class template <code>variate_generator</code> model a
- number generator.</p>
-
- <p>The argument for the template parameter <code>Engine</code> shall be of
- the form U, U&, or U*, where U models a uniform random number
- generator. Then, the member <code>engine_value_type</code> names U (not the
- pointer or reference to U).</p>
-
- <p>Specializations of <code>variate_generator</code> satisfy the
- requirements of CopyConstructible. They also satisfy the requirements of
- Assignable unless the template parameter Engine is of the form U&.</p>
-
- <p>The complexity of all functions specified in this section is constant.
- No function described in this section except the constructor throws an
- exception.</p>
- <pre>
- variate_generator(engine_type eng, distribution_type d)
-</pre>
-
- <p><strong>Effects:</strong> Constructs a <code>variate_generator</code>
- object with the associated uniform random number generator <code>eng</code>
- and the associated random distribution <code>d</code>.<br>
- <strong>Throws:</strong> If and what the copy constructor of Engine or
- Distribution throws.</p>
- <pre>
- result_type operator()()
-</pre>
-
- <p><strong>Returns:</strong> <code>distribution()(e)</code><br>
- <strong>Notes:</strong> The sequence of numbers produced by the uniform
- random number generator <code>e</code>, s<sub>e</sub>, is obtained from the
- sequence of numbers produced by the associated uniform random number
- generator <code>eng</code>, s<sub>eng</sub>, as follows: Consider the
- values of <code>numeric_limits<<em>T</em>>::is_integer</code> for
- <code><em>T</em></code> both <code>Distribution::input_type</code> and
- <code>engine_value_type::result_type</code>. If the values for both types
- are <code>true</code>, then s<sub>e</sub> is identical to s<sub>eng</sub>.
- Otherwise, if the values for both types are <code>false</code>, then the
- numbers in s<sub>eng</sub> are divided by
- <code>engine().max()-engine().min()</code> to obtain the numbers in
- s<sub>e</sub>. Otherwise, if the value for
- <code>engine_value_type::result_type</code> is <code>true</code> and the
- value for <code>Distribution::input_type</code> is <code>false</code>, then
- the numbers in s<sub>eng</sub> are divided by
- <code>engine().max()-engine().min()+1</code> to obtain the numbers in
- s<sub>e</sub>. Otherwise, the mapping from s<sub>eng</sub> to s<sub>e</sub>
- is implementation-defined. In all cases, an implicit conversion from
- <code>engine_value_type::result_type</code> to
- <code>Distribution::input_type</code> is performed. If such a conversion
- does not exist, the program is ill-formed.</p>
- <pre>
- template<class T> result_type operator()(T value)
-</pre>
-
- <p><strong>Returns:</strong> <code>distribution()(e, value)</code>. For the
- semantics of <code>e</code>, see the description of
- <code>operator()()</code>.</p>
- <pre>
- engine_value_type& engine()
-</pre>
-
- <p><strong>Returns:</strong> A reference to the associated uniform random
- number generator.</p>
- <pre>
- const engine_value_type& engine() const
-</pre>
-
- <p><strong>Returns:</strong> A reference to the associated uniform random
- number generator.</p>
- <pre>
- distribution_type& distribution()
-</pre>
-
- <p><strong>Returns:</strong> A reference to the associated random
- distribution.</p>
- <pre>
- const distribution_type& distribution() const
-</pre>
-
- <p><strong>Returns:</strong> A reference to the associated random
- distribution.</p>
- <pre>
- result_type min() const
-</pre>
-
- <p><strong>Precondition:</strong> <code>distribution().min()</code> is
- well-formed<br>
- <strong>Returns:</strong> <code>distribution().min()</code></p>
- <pre>
- result_type max() const
-</pre>
-
- <p><strong>Precondition:</strong> <code>distribution().max()</code> is
- well-formed<br>
- <strong>Returns:</strong> <code>distribution().max()</code></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
- 05
- December, 2006</p>
-
- <p><i>Copyright © 2003-2004 <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 LICENSE_1_0.txt or
- copy at <a href=
- "http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt>)</i></p>
-</body>
-</html>

Deleted: trunk/libs/random/wg21-proposal.html
==============================================================================
--- trunk/libs/random/wg21-proposal.html 2010-03-04 23:59:16 EST (Thu, 04 Mar 2010)
+++ (empty file)
@@ -1,3608 +0,0 @@
-<!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>A Proposal to Add an Extensible Random Number Facility to the
- Standard Library</title>
-</head>
-
-<body bgcolor="#FFFFFF" text="#000000">
- <font size="-1">Jens Maurer <Jens.Maurer_at_[hidden]><br>
- 2002-11-10<br>
- Document N1398=02-0056</font>
-
- <p><font size="-1"><code>$Id: proposal.html,v 1.44 2002/11/10 20:42:15
- jmaurer Exp $</code></font></p>
-
- <h1>A Proposal to Add an Extensible Random Number Facility to the Standard
- Library (N1398)</h1>
-
- <blockquote>
- Any one who considers arithmetical methods of producing random digits is,
- of course, in a state of sin.
- </blockquote>
-
- <p align="right">John von Neumann, 1951</p>
-
- <h2>Revision history</h2>
-
- <ul>
- <li>2002-11-10: Publication in the Post-Santa Cruz mailing.</li>
-
- <li>The <code>seed(first, last)</code> interface now needs "unsigned
- long" values.</li>
-
- <li>Introduce "variate_generator", adjust distribution interface
- accordingly.</li>
-
- <li>Add "add-on packages" discussion.</li>
-
- <li>All distribution parameters must be defaulted.</li>
-
- <li>Add "target audience" subsection to "motivation" section.</li>
-
- <li>Add discussion of manager class.</li>
-
- <li>Engines are independent of distributions, thus consider respective
- lifetimes.</li>
-
- <li>Add "sharing of engines" as a major requirement.</li>
-
- <li>Add some open issues.</li>
-
- <li>2002-10-11: First publication on the C++ committee's library
- reflector.</li>
- </ul>
-
- <h2>I. Motivation</h2>
-
- <blockquote>
- <i>Why is this important? What kinds of problems does it address, and
- what kinds of programmers, is it intended to support? Is it based on
- existing practice?</i>
- </blockquote>Computers are deterministic machines by design: equal input
- data results in equal output, given the same internal state. Sometimes,
- applications require seemingly non-deterministic behaviour, usually
- provided by generating random numbers. Such applications include:
-
- <ul>
- <li>numerics (simulation, Monte-Carlo integration)</li>
-
- <li>games (shuffling card decks, non-deterministic enemy behavior)</li>
-
- <li>testing (generation of test input data for good coverage)</li>
-
- <li>security (generation of cryptographic keys)</li>
- </ul>
-
- <p>Programmers in all of the above areas have to find ways to generate
- random numbers. However, the difficulty to find generators that are both
- efficient and have good quality is often underestimated, and so ad-hoc
- implementations often fail to meet either or both of these goals.</p>
-
- <p>The C++ standard library includes <code>std::rand</code>, inherited from
- the C standard library, as the only facility to generate pseudo-random
- numbers. It is underspecified, because the generation function is not
- defined, and indeed early C standard library implementations provided
- surprisingly bad generators. Furthermore, the interface relies on global
- state, making it difficult or inefficient to provide for correct operation
- for simultaneous invocations in multi-threaded applications.</p>
-
- <p>There is a lot of existing practice in this area. A multitude of
- libraries, usually implemented in C or Fortran, is available from the
- scientific community. Some implement just one random number engine, others
- seek to provide a full framework. I know of no comprehensive C++ framework
- for generating random numbers that adheres to the design principles put
- forth in section III.</p>
-
- <p>Random number generators are appropriate for this TR because they fall
- into one of the domains (numerics) identified in N1314 as a target for the
- TR.</p>
-
- <h3>Target Audience</h3>There are several different kinds of programmers
- that are assumed to use the facilities provided in this proposal.
-
- <ul>
- <li>programmers that provide additional engines</li>
-
- <li>programmers that provide additional distributions</li>
-
- <li>programmers that provide generic add-on packages</li>
-
- <li>programmers that need random numbers</li>
- </ul>This proposal specifies an infrastructure so that the needs of all
- four groups are met. The first two groups benefit from a modular design so
- that they can plug in their contributions. Providing add-on packages
- benefits from a design that suits to generic programming needs. Finally,
- users in need of random numbers benefit from an interface to the package
- that is easy to use.
-
- <h2>II. Impact On the Standard</h2>
-
- <blockquote>
- <i>What does it depend on, and what depends on it? Is it a pure
- extension, or does it require changes to standard components? Does it
- require core language changes?</i>
- </blockquote>This proposal is a pure library extension. It does not require
- changes to any standard classes or functions. It does not require changes
- to any of the standard requirement tables. It does not require any changes
- in the core language, and it has been implemented in standard C++ as per
- ISO 14882:1998.
-
- <p>The ISO C99 extension that specify integral types having a given minimum
- or exact bitwidth (e.g. <code>int32_t</code>) aids in implementing this
- proposal, however these types (or the equivalent thereof under another
- name) can be defined with template metaprogramming in standard C++, so
- these are not strictly necessary.</p>
-
- <p>In case the ISO C99 extensions become part of the TR, section IV should
- be reviewed whether some requirements could be reformulated with the ISO
- C99 extensions.</p>
-
- <p>In case a standard reference-counted smart pointer becomes part of the
- TR, section IV should be reviewed and instances of the smart pointer be
- added to the acceptable template parameters for a
- <code>variate_generator</code>.</p>
-
- <h2>III. Design Decisions</h2>
-
- <blockquote>
- <i>Why did you choose the specific design that you did? What alternatives
- did you consider, and what are the tradeoffs? What are the consequences
- of your choice, for users and implementors? What decisions are left up to
- implementors? If there are any similar libraries in use, how do their
- design decisions compare to yours?</i>
- </blockquote>The design decisions are compared to those in the following
- libraries:
-
- <ul>
- <li>CLHEP (original at http://wwwinfo.cern.ch/asd/lhc++/clhep/index.html,
- modifications from FermiLab at (anonymous CVS)
- :pserver:anonymous_at_[hidden]:/usr/people/cvsuser/repository)</li>
-
- <li>crng 1.1: Random-number generators (RNGs) implemented as Python
- extension types coded in C (at http://www.sbc.su.se/~per/crng/)</li>
-
- <li>Swarm 2.1.1 (multi-agent simulation of complex systems), random
- number package, using a Smalltalk-like programming language (at
- http://www.santafe.edu/projects/swarm/swarmdocs/set/swarm.random.sgml.reference.html)</li>
-
- <li>GNU Scientific Library: general scientific computing library
- implemented in C, comprehensive coverage of random number engines and
- distributions (at http://sources.redhat.com/gsl)</li>
- </ul>The choice of engines and distributions is also contrasted against the
- following literature:
-
- <ul>
- <li>Donald E. Knuth, "The Art of Computer Programming Vol. 2"</li>
-
- <li>William H. Press et al., "Numerical Recipes in C"</li>
- </ul>
-
- <h3>A. Overview on Requirements</h3>Here is a short overview on the
- requirements for the random number framework.
-
- <ul>
- <li>allows users to choose in speed / size / quality trade-offs</li>
-
- <li>has a tight enough specification to get reliable cross-platform
- results</li>
-
- <li>allows storage of state on non-volatile media (e.g., in a disk file)
- to resume computation later</li>
-
- <li>does not impede sequence "jump-ahead" for parallel computation</li>
-
- <li>provides a variety of base engines, not just one</li>
-
- <li>allows the user to write its own base engines and use it with the
- library-provided distributions</li>
-
- <li>provides the most popular distributions</li>
-
- <li>allows the user to write its own distributions and use it with the
- library-provided engines</li>
-
- <li>allows sharing of engines by several distributions</li>
-
- <li>does not prevent implementations with utmost efficiency</li>
-
- <li>provides both pseudo-random number engines (for simulations etc.) and
- "true" non-deterministic random numbers (for cryptography)</li>
- </ul>All of the requirements are revisited in detail in the following
- sections.
-
- <h3>B. Pseudo-Random vs. Non-Deterministic Random Numbers</h3>This section
- tries to avoid philosophical discussions about randomness as much as
- possible, a certain amount of intuition is assumed.
-
- <p>In this proposal, a <em>pseudo-random number engine</em> is defined as
- an initial internal state x(0), a function f that moves from one internal
- state to the next x(i+1) := f(x(i)), and an output function o that produces
- the output o(x(i)) of the generator. This is an entirely deterministic
- process, it is determined by the initial state x(0) and functions f and o
- only. The initial state x(0) is determined from a seed. Apparent randomness
- is achieved only because the user has limited perception.</p>
-
- <p>A <em>non-deterministic random-number engine</em> provides a sequence of
- random numbers x(i) that cannot be foreseen. Examples are certain
- quantum-level physics experiments, measuring the time difference between
- radioactive decay of individual atoms or noise of a Zehner diode.
- Relatively unforeseeable random sources are also (the low bits of) timing
- between key touches, mouse movements, Ethernet packet arrivals, etc. An
- estimate for the amount of unforeseeability is the entropy, a concept from
- information theory. Completely foreseeable sequences (e.g., from
- pseudo-random number engines) have entropy 0, if all bits are
- unforeseeable, the entropy is equal to the number of bits in each
- number.</p>
-
- <p>Pseudo-random number engines are usually much faster than
- non-deterministic random-number engines, because the latter require I/O to
- query some randomness device outside of the computer. However, there is a
- common interface feature subset of both pseudo-random and non-deterministic
- random-number engines. For example, a non-deterministic random-number
- engine could be employed to produce random numbers with normal
- distribution; I believe this to be an unlikely scenario in practice.</p>
-
- <p>Other libraries, including those mentioned above, only provide either
- pseudo-random numbers, suitable for simulations and games, or
- non-deterministic random numbers, suitable for cryptographic
- applications.</p>
-
- <h3>C. Separation of Engines and Distributions</h3>Random-number generation
- is usually conceptually separated into <em>random-number engines</em> that
- produce uniformly distributed random numbers between a given minimum and
- maximum and <em>random-number distributions</em> that retrieve uniformly
- distributed random numbers from some engine and produce numbers according
- to some distribution (e.g., Gaussian normal or Bernoulli distribution).
- Returning to the formalism from section A, the former can be identified
- with the function f and the latter with the output function o.
-
- <p>This proposal honours this conceptual separation, and provides a class
- template to merge an arbitrary engine with an arbitrary distribution on
- top. To this end, this proposal sets up requirements for engines so that
- each of them can be used to provide uniformly distributed random numbers
- for any of the distributions. The resulting freedom of combination allows
- for the utmost re-use.</p>
-
- <p>Engines have usually been analyzed with all mathematical and empirical
- tools currently available. Nonetheless, those tools show the absence of a
- particular weakness only, and are not exhaustive. Albeit unlikely, a new
- kind of test (for example, a use of random numbers in a new kind of
- simulation or game) could show serious weaknesses in some engines that were
- not known before.</p>
-
- <p>This proposal attempts to specify the engines precisely; two different
- implementations, with the same seed, should return the same output
- sequence. This forces implementations to use the well-researched engines
- specified hereinafter, and users can have confidence in their quality and
- the limits thereof.</p>
-
- <p>On the other hand, the specifications for the distributions only define
- the statistical result, not the precise algorithm to use. This is different
- from engines, because for distribution algorithms, rigorous proofs of their
- correctness are available, usually under the precondition that the input
- random numbers are (truely) uniformly distributed. For example, there are
- at least a handful of algorithms known to produce normally distributed
- random numbers from uniformly distributed ones. Which one of these is most
- efficient depends on at least the relative execution speeds for various
- transcendental functions, cache and branch prediction behaviour of the CPU,
- and desired memory use. This proposal therefore leaves the choice of the
- algorithm to the implementation. It follows that output sequences for the
- distributions will not be identical across implementations. It is expected
- that implementations will carefully choose the algorithms for distributions
- up front, since it is certainly surprising to customers if some
- distribution produces different numbers from one implementation version to
- the next.</p>
-
- <p>Other libraries usually provide the same differentiation between engines
- and distributions. Libraries rarely have a wrapper around both engine and
- distribution, but it turns out that this can hide some complexities from
- the authors of distributions, since some facitilies need to be provided
- only once. A previous version of this proposal had distributions directly
- exposed to the user, and the distribution type dependent on the engine
- type. In various discussions, this was considered as too much coupling.</p>
-
- <p>Since other libraries do not aim to provide a portable specification
- framework, engines are sometimes only described qualitatively without
- giving the exact parameterization. Also, distributions are given as
- specific functions or classes, so the quality-of-implementation question
- which distribution algorithm to employ does not need to be addressed.</p>
-
- <h3>D. Templates vs. Virtual Functions</h3>The layering sketched in the
- previous subsection can be implemented by either a template mechanism or by
- using virtual functions in a class hierarchy. This proposal uses templates.
- Template parameters are usually some base type and values denoting fixed
- parameters for the functions f and o, e.g. a word size or modulus.
-
- <p>For virtual functions in a class hierarchy, the core language requires a
- (nearly) exact type match for a function in a derived classes overriding a
- function in a base class. This seems to be unnecessarily restrictive,
- because engines can sometimes benefit from using different integral base
- types. Also, with current compiler technology, virtual functions prevent
- inlining when a pointer to the base class is used to call a virtual
- function that is overridden in some derived class. In particular with
- applications such as simulations that sometimes use millions of
- pseudo-random numbers per second, losing significant amounts of performance
- due to missed inlining opportunities appears to not be acceptable.</p>
-
- <p>The CLHEP library bases all its engines on the abstract base class
- <code>HepRandomEngine</code>. Specific engines derive from this class and
- override its pure virtual functions. Similarly, all distributions are based
- on the base class <code>HepRandom</code>. Specific distributions derive
- from this class, override operator(), and provide a number of specific
- non-virtual functions.</p>
-
- <p>The GNU Scientific Library, while coded in C, adheres to the principles
- of object-structuring; all engines can be used with any of the
- distributions. The technical implementation is by mechanisms similar to
- virtual functions.</p>
-
- <h3>E. Parameterization and Initialization for Engines</h3>Engines usually
- have a "base" type which is used to store its internal state. Also, they
- usually have a choice of parameters. For example, a linear congruential
- engine is defined by x(i+1) = (a*x(i)+c) mod m, so f(x) = (a*x+c) mod m;
- the base type is "int" and parameters are a, c, and m. Finding parameters
- for a given function f that make for good randomness in the resulting
- engine's generated numbers x(i) requires extensive and specialized
- mathematical training and experience. In order to make good random numbers
- available to a large number of library users, this proposal not only
- defines generic random-number engines, but also provides a number of
- predefined well-known good parameterizations for those. Usually, there are
- only a few (less than five) well-known good parameterizations for each
- engine, so it appears feasible to provide these.
-
- <p>Since random-number engines are mathematically designed with computer
- implementation in mind, parameters are usually integers representable in a
- machine word, which usually coincides nicely with a C++ built-in type. The
- parameters could either be given as (compile-time) template arguments or as
- (run-time) constructor arguments.</p>
-
- <p>Providing parameters as template arguments allows for providing
- predefined parameterizations as simple "typedef"s. Furthermore, the
- parameters appear as integral constants, so the compiler can value-check
- the given constants against the engine's base type. Also, the library
- implementor can choose different implementations depending on the values of
- the parameters, without incurring any runtime overhead. For example, there
- is an efficient method to compute (a*x) mod m, provided that a certain
- magnitude of m relative to the underlying type is not exceeded.
- Additionally, the compiler's optimizer can benefit from the constants and
- potentially produce better code, for example by unrolling loops with fixed
- loop count.</p>
-
- <p>As an alternative, providing parameters as constructor arguments allows
- for more flexibility for the library user, for example when experimenting
- with several parameterizations. Predefined parameterizations can be
- provided by defining wrapper types which default the constructor
- parameters.</p>
-
- <p>Other libraries have hard-coded the parameters of their engines and do
- not allow the user any configuration of them at all. If the user wishes to
- change the parameters, he has to re-implement the engine's algorithm. In my
- opinion, this approach unnecessarily restricts re-use.</p>
-
- <p>Regarding initialization, this proposal chooses to provide
- "deterministic seeding" with the default constructor and the
- <code>seed</code> function without parameters: Two engines constructed
- using the default constructor will output the same sequence. In contrast,
- the CLHEP library's default constructed engines will take a fresh seed from
- a seed table for each instance. While this approach may be convenient for a
- certain group of users, it relies on global state and can easily be
- emulated by appropriately wrapping engines with deterministic seeding.</p>
-
- <p>In addition to the default constructor, all engines provide a
- constructor and <code>seed</code> function taking an iterator range
- [it1,it2) pointing to unsigned integral values. An engine initializes its
- state by successively consuming values from the iterator range, then
- returning the advanced iterator it1. This approach has the advantage that
- the user can completely exploit the large state of some engines for
- initialization. Also, it allows to initialize compound engines in a uniform
- manner. For example, a compound engine consisting of two simpler engines
- would initialize the first engine with its [it1,it2). The first engine
- returns a smaller iterator range that it has not consumed yet. This can be
- used to initialize the second engine.</p>
-
- <p>The iterator range [it1,it2) is specified to point to unsigned long
- values. There is no way to determine from a generic user program how the
- initialization values will be treated and what range of bits must be
- provided, except by enumerating all engines, e.g. in template
- specializations. The problem is that a given generator might have differing
- requirements on the values of the seed range even within one
- <code>seed</code> call.</p>
-
- <p>For example, imagine a</p>
- <pre>
- xor_combine<lagged_fibonacci<...>, mersenne_twister<...> >
-</pre>generator. For this, <code>seed(first, last)</code> will consume values
-as follows: First, seed the state of the <code>lagged_fibonacci</code>
-generator by consuming one item from [first, last) for each word of state.
-The values are reduced to (e.g.) 24 bits to fit the
-<code>lagged_fibonacci</code> state requirements. Then, seed the state of the
-<code>mersenne_twister</code> by consuming some number of items from the
-remaining [first, last). The values are reduced to 32 bits to fit the <code>
- mersenne_twister</code> state requirements.
-
- <p>How does a concise programming interface for those increasingly complex
- and varying requirements on [first, last) look like? I don't know, and I
- don't want to complicate the specification by inventing something
- complicated here.</p>
-
- <p>Thus, the specification says for each generator how it uses the seed
- values, and how many are consumed. Additional features are left to the
- user.</p>
-
- <p>In a way, this is similar to STL containers: It is intended that the
- user can exchange iterators to various containers in generic algorithms,
- but the container itself is not meant to be exchanged, i.e. having a
- Container template parameter is often not adequate. That is analogous to
- the random number case: The user can pass an engine around and use its
- <code>operator()</code> and <code>min</code> and <code>max</code> functions
- generically. However, the user can't generically query the engine
- attributes and parameters, simply because most are entirely different in
- semantics for each engine.</p>
-
- <p>The <code>seed(first, last)</code> interface can serve two purposes:</p>
-
- <ol>
- <li>In a generic context, the user can pass several integer values >=
- 1 for seeding. It is unlikely that the user explores the full state space
- with the seeds she provides, but she can be reasonably sure that her
- seeds aren't entirely incorrect. (There is no formal guarantee for that,
- except that the ability to provide bad seeds usually means the
- parameterization of the engine is bad, e.g. a non-prime modulus for a
- linear congruential engine.) For example, if the user wants a
- <code>seed(uint32_t)</code> on top of <code>seed(first, last)</code>, one
- option is to use a <code>linear_congruential</code> generator that
- produces the values required for <code>seed(first, last)</code>. When the
- user defines the iterator type for <code>first</code> and
- <code>last</code> so that it encapsulates the
- <code>linear_congruential</code> engine in <code>operator++</code>, the
- user doesn't even need to know beforehand how many values
- <code>seed(first, last)</code> will need.</li>
-
- <li>If the user is in a non-generic context, he knows the specific
- template type of the engine (probably not the template value-based
- parameterization, though). The precise specification for
- <code>seed(first, last)</code> allows to know what values need to be
- passed in so that a specific initial state is attained, for example to
- compare one implementation of the engine with another one that uses
- different seeding.</li>
-
- <li>If the user requires both, he needs to inject knowledge into (1) so
- that he is in the position of (2). One way to inject the knowledge is to
- use (partial) template specialization to add the knowledge. The specific
- parameterization of some engine can then be obtained by querying the data
- members of the engines.</li>
- </ol>
-
- <p>I haven't seen the iterator-based approach to engine initialization in
- other libraries; most initialization approaches rely on a either a single
- value or on per-engine specific approaches to initialization.</p>
-
- <p>An alternative approach is to pass a zero-argument function object
- ("generator") for seeding. It is trivial to implement a generator from a
- given iterator range, but it is more complicated to implement an iterator
- range from a generator. Also, the exception object that is specified to be
- thrown when the iterator range is exhausted could be configured in a
- user-provided iterator to generator mapping. With this approach, some
- engines would have three one-argument constructors: One taking a single
- integer for seeding, one taking a (reference?) to a (templated) generator,
- and the copy constructor. It appears that the opportunities for ambiguities
- or choosing the wrong overload are too confusing to the unsuspecting
- user.</p>
-
- <h3>F. Parameterization and Initialization for Distributions</h3>The
- distributions specified in this proposal have template parameters that
- indicate the output data type (e.g. <code>float</code>,
- <code>double</code>, <code>long double</code>) that the user desires.
-
- <p>The probability density functions of distributions usually have
- parameters. These are mapped to constructor parameters, to be set at
- runtime by the library user according to her requirements. The parameters
- for a distribution object cannot change after its construction. When
- constructing the distribution, this allows to pre-compute some data
- according to the parameters given without risk of inadvertently
- invalidating them later.</p>
-
- <p>Distributions may implement <code>operator()(T x)</code>, for arbitrary
- type <code>T</code>, to meet special needs, for example a "one-shot" mode
- where each invocation uses different distribution parameters.</p>
-
- <h3>G. Properties as Traits vs. In-Class Constants</h3>Users might wish to
- query compile-time properties of the engines and distributions, e.g. their
- base types, constant parameters, etc. This is similar to querying the
- properties of the built-in types such as <code>double</code> using
- <code>std::numeric_limits<></code>. However, engines and
- distributions cannot be simple types, so it does not appear to be necessary
- to separate the properties into separate traits classes. Instead,
- compile-time properties are given as members types and static member
- constants.
-
- <h3>H. Which Engines to Include</h3>There is a multitude of pseudo-random
- number engines available in both literature and code. Some engines, such as
- Mersenne Twister, have an independent algorithm ("base engine"). Others
- change the values or order of output of other engines to improve
- randomness, for example Knuth's "Algorithm B" ("compound engine"). The
- template mechanism allows easy combination of base and compound engines.
-
- <p>Engines may be categorized according to the following dimensions.</p>
-
- <ul>
- <li>integers or floating-point numbers produced (Some engines produce
- uniformly distributed integers in the range [min,max], however, most
- distribution functions expect uniformly distributed floating-point
- numbers in the range [0,1) as the input sequence. The obvious conversion
- requires a relatively costly integer to floating-point conversion plus a
- floating-point multiplication by (max-min+1)<sup>-1</sup> for each random
- number used. To save the multiplication, some engines can directly
- produce floating-point numbers in the range [0,1) by maintaining the
- state x(i) in an appropriately normalized form, given a sufficiently good
- implementation of basic floating-point operations (e.g. IEEE 754).</li>
-
- <li>quality of random numbers produced (What is the cycle length? Does
- the engine pass all relevant statistical tests? Up to what dimension are
- numbers equidistributed?)</li>
-
- <li>speed of generation (How many and what kind of operations have to be
- performed to produce one random number, on average?)</li>
-
- <li>size of state (How may machine words of storage are required to hold
- the state x(i) of the random engine?)</li>
-
- <li>option for independent subsequences (Is it possible to move from x(i)
- to x(i+k) with at most O(log(k)) steps? This allows to efficiently use
- subsequences x(0)...x(k-1), x(k)...x(2k-1), ..., x(jk)...x((j+1)k-1),
- ..., for example for parallel computation, where each of the m processors
- gets assigned the (independent) subsequence starting at x(jk) (0 <= k
- < m).)</li>
- </ul>According to the criteria above, the engines given below were chosen.
- The quality and size indications were completed according to best known
- parameterizations. Other parameterizations usually yield poorer quality
- and/or less size.
-
- <table border="1" summary="">
- <tr>
- <th>engine</th>
-
- <th>int / float</th>
-
- <th>quality</th>
-
- <th>speed</th>
-
- <th>size of state</th>
-
- <th>subsequences</th>
-
- <th>comments</th>
- </tr>
-
- <tr>
- <td>linear_congruential</td>
-
- <td>int</td>
-
- <td>medium</td>
-
- <td>medium</td>
-
- <td>1 word</td>
-
- <td>yes</td>
-
- <td>cycle length is limited to the maximum value representable in one
- machine word, passes most statisticial tests with chosen
- parameters.</td>
- </tr>
-
- <tr>
- <td>mersenne_twister</td>
-
- <td>int</td>
-
- <td>good</td>
-
- <td>fast</td>
-
- <td>624 words</td>
-
- <td>no</td>
-
- <td>long cycles, passes all statistical tests, good equidistribution in
- high dimensions</td>
- </tr>
-
- <tr>
- <td>subtract_with_carry</td>
-
- <td>both</td>
-
- <td>medium</td>
-
- <td>fast</td>
-
- <td>25 words</td>
-
- <td>no</td>
-
- <td>very long cycles possible, fails some statistical tests. Can be
- improved with the discard_block compound engine.</td>
- </tr>
-
- <tr>
- <td>discard_block</td>
-
- <td>both</td>
-
- <td>good</td>
-
- <td>slow</td>
-
- <td>base engine + 1 word</td>
-
- <td>no</td>
-
- <td>compound engine that removes correlation provably by throwing away
- significant chunks of the base engine's sequence, the resulting speed
- is reduced to 10% to 3% of the base engine's.</td>
- </tr>
-
- <tr>
- <td>xor_combine</td>
-
- <td>int</td>
-
- <td>good</td>
-
- <td>fast</td>
-
- <td>base engines</td>
-
- <td>yes, if one of the base engines</td>
-
- <td>compound engine that XOR-combines the sequences of two base
- engines</td>
- </tr>
- </table>
-
- <p>Some engines were considered for inclusion, but left out for the
- following reasons:</p>
-
- <table border="1" summary="">
- <tr>
- <th>engine</th>
-
- <th>int / float</th>
-
- <th>quality</th>
-
- <th>speed</th>
-
- <th>size of state</th>
-
- <th>subsequences</th>
-
- <th>comments</th>
- </tr>
-
- <tr>
- <td>shuffle_output</td>
-
- <td>int</td>
-
- <td>good</td>
-
- <td>fast</td>
-
- <td>base engine + 100 words</td>
-
- <td>no</td>
-
- <td>compound engine that reorders the base engine's output, little
- overhead for generation (one multiplication)</td>
- </tr>
-
- <tr>
- <td>lagged_fibonacci</td>
-
- <td>both</td>
-
- <td>medium</td>
-
- <td>fast</td>
-
- <td>up to 80,000 words</td>
-
- <td>no</td>
-
- <td>very long cycles possible, fails birthday spacings test. Same
- principle of generation as <code>subtract_with_carry</code>, i.e. x(i)
- = x(i-s) (*) x(i-r), where (*) is either of +, -, xor with or without
- carry.</td>
- </tr>
-
- <tr>
- <td>inversive_congruential (Hellekalek 1995)</td>
-
- <td>int</td>
-
- <td>good</td>
-
- <td>slow</td>
-
- <td>1 word</td>
-
- <td>no</td>
-
- <td>x(i+1) = a x(i)<sup>-1</sup> + c. Good equidistribution in several
- dimensions. Provides no apparent advantage compared to ranlux; the
- latter can produce floating-point numbers directly.</td>
- </tr>
-
- <tr>
- <td>additive_combine (L'Ecuyer 1988)</td>
-
- <td>int</td>
-
- <td>good</td>
-
- <td>medium</td>
-
- <td>2 words</td>
-
- <td>yes</td>
-
- <td>Combines two linear congruential generators. Same principle of
- combination as <code>xor_combine</code>, i.e. z(i) = x(i) (*) y(i),
- where (*) is one of +, -, xor.</td>
- </tr>
-
- <tr>
- <td>R250 (Kirkpatrick and Stoll)</td>
-
- <td>int</td>
-
- <td>bad</td>
-
- <td>fast</td>
-
- <td>~ 20 words</td>
-
- <td>no</td>
-
- <td>General Feedback Shift Register with two taps: Easily exploitable
- correlation.</td>
- </tr>
-
- <tr>
- <td>linear_feedback_shift</td>
-
- <td>int</td>
-
- <td>medium</td>
-
- <td>fast</td>
-
- <td>1 word</td>
-
- <td>no</td>
-
- <td>cycle length is limited to the maximum value representable in one
- machine word, fails some statistical tests, can be improved with the
- xor_combine compound engine.</td>
- </tr>
- </table>
-
- <p>The GNU Scientific Library and Swarm have additional engine that are not
- mentioned in the table below.</p>
-
- <table border="1" summary="">
- <tr>
- <th>Engine</th>
-
- <th>this proposal</th>
-
- <th>CLHEP</th>
-
- <th>crng</th>
-
- <th>GNU Scientific Library</th>
-
- <th>Swarm</th>
-
- <th>Numerical Recipes</th>
-
- <th>Knuth</th>
- </tr>
-
- <tr>
- <td>LCG(2<sup>31</sup>-1, 16807)</td>
-
- <td>minstd_rand0</td>
-
- <td>-</td>
-
- <td>ParkMiller</td>
-
- <td>ran0, minstd</td>
-
- <td>-</td>
-
- <td>ran0</td>
-
- <td>p106, table 1, line 19</td>
- </tr>
-
- <tr>
- <td>LCG(2<sup>32</sup>, a=1664525, c=1013904223)</td>
-
- <td>linear_congruential< ..., 1664525, 1013904223, (1 << 32)
- ></td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>LCG1gen</td>
-
- <td>-</td>
-
- <td>p106, table 1, line 16</td>
- </tr>
-
- <tr>
- <td>LCG1 + LCG2 + LCG3</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>WichmannHill</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>-</td>
- </tr>
-
- <tr>
- <td>(LCG1 - LCG2 + LCG3 - LCG4) mod m0</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>C4LCGXgen</td>
-
- <td>-</td>
-
- <td>-</td>
- </tr>
-
- <tr>
- <td>LCG(2<sup>31</sup>-1, 16807) with Bays/Durham shuffle</td>
-
- <td>shuffle_output<minstd_rand0, 32> (shuffle_output not in this
- proposal)</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>ran1</td>
-
- <td>PMMLCG1gen</td>
-
- <td>ran1</td>
-
- <td>Algorithm "B"</td>
- </tr>
-
- <tr>
- <td>(LCG(2<sup>31</sup>-85, 40014) + LCG(2<sup>31</sup>-249, 40692))
- mod 2<sup>31</sup>-85</td>
-
- <td>ecuyer1988 (additive_combine not in this proposal)</td>
-
- <td>Ranecu</td>
-
- <td>LEcuyer</td>
-
- <td>-</td>
-
- <td>C2LCGXgen</td>
-
- <td>-</td>
-
- <td>-</td>
- </tr>
-
- <tr>
- <td>(LCG(2<sup>31</sup>-85, 40014) with Bays/Durham shuffle +
- LCG(2<sup>31</sup>-249, 40692)) mod 2<sup>31</sup>-85</td>
-
- <td>additive_combine< shuffle_output<<br>
- linear_congruential<int, 40014, 0, 2147483563>, 32>,<br>
- linear_congruential<int, 40692, 0, 2147483399> >
- (additive_combine and shuffle_output not in this proposal)</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>ran2</td>
-
- <td>-</td>
-
- <td>ran2</td>
-
- <td>-</td>
- </tr>
-
- <tr>
- <td>X(i) = (X(i-55) - X(i-33)) mod 10<sup>9</sup></td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>ran3</td>
-
- <td>~SCGgen</td>
-
- <td>ran3</td>
-
- <td>-</td>
- </tr>
-
- <tr>
- <td>X(i) = (X(i-100) - X(i-37)) mod 2<sup>30</sup></td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>ran_array</td>
- </tr>
-
- <tr>
- <td>X(i) = (X(i-55) + X(i-24)) mod 2<sup>32</sup></td>
-
- <td>lagged_fibonacci< ..., 32, 55, 24, ...> (lagged_fibonacci not
- in this proposal)</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>ACGgen</td>
-
- <td>-</td>
-
- <td>-</td>
- </tr>
-
- <tr>
- <td>DEShash(i,j)</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>ran4</td>
-
- <td>-</td>
- </tr>
-
- <tr>
- <td>MT</td>
-
- <td>mt19937</td>
-
- <td>MTwistEngine</td>
-
- <td>MT19937</td>
-
- <td>mt19937</td>
-
- <td>MT19937gen</td>
-
- <td>-</td>
-
- <td>-</td>
- </tr>
-
- <tr>
- <td>X(i) = (X(i-37) - X(i-24) - carry) mod 2<sup>32</sup></td>
-
- <td>subtract_with_carry< ..., (1<<32), 37, 24, ...></td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>SWB1gen</td>
-
- <td>-</td>
-
- <td>-</td>
- </tr>
-
- <tr>
- <td>X(i) = (X(i-43) - X(i-22) - carry) mod 2<sup>32</sup>-5</td>
-
- <td>subtract_with_carry< ..., (1<<32)-5, 43, 22, ...></td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>PSWBgen</td>
-
- <td>-</td>
-
- <td>-</td>
- </tr>
-
- <tr>
- <td>RCARRY with block discard by Lüscher</td>
-
- <td>discard_block< subtract_with_carry<...>, ...></td>
-
- <td>RanluxEngine, Ranlux64Engine</td>
-
- <td>Ranlux</td>
-
- <td>ranlx*</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>-</td>
- </tr>
-
- <tr>
- <td>Hurd</td>
-
- <td>-</td>
-
- <td>Hurd160, Hurd288</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>-</td>
- </tr>
-
- <tr>
- <td>physical model by Ranshi</td>
-
- <td>-</td>
-
- <td>Ranshi</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>-</td>
- </tr>
-
- <tr>
- <td>return predefined data</td>
-
- <td>-</td>
-
- <td>NonRandom</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>-</td>
- </tr>
-
- <tr>
- <td>RANMAR: z(i) = (z(i-97) - z(i-33)) mod 2<sup>24</sup>; y(i+1) =
- (y(i)-c) mod 2<sup>24</sup>-3; X(i) = (z(i) - y(i)) mod
- 2<sup>24</sup></td>
-
- <td>additive_combine< lagged_fibonacci< (1<<24), 97, 33,
- ... >, linear_congruential< (1<<24)-3, 1, c, ...>
- (additive_combine and lagged_fibonacci not in this proposal)</td>
-
- <td>JamesRandom</td>
-
- <td>-</td>
-
- <td>ranmar</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>-</td>
- </tr>
-
- <tr>
- <td>Taus88</td>
-
- <td>taus88 = xor_combine ...</td>
-
- <td>-</td>
-
- <td>Taus88</td>
-
- <td>taus, taus2</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>-</td>
- </tr>
-
- <tr>
- <td>Taus60</td>
-
- <td>xor_combine< linear_feedback_shift< 31, 13, 12 >, 0,
- linear_feedback_shift< 29, 2, 4 >, 2, 0>
- (linear_feedback_shift not in this proposal)</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>C2TAUSgen</td>
-
- <td>-</td>
-
- <td>-</td>
- </tr>
-
- <tr>
- <td>GFSR, 4-tap</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>gfsr4</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>-</td>
- </tr>
-
- <tr>
- <td>MRG32k3a</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>MRG32k3a</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>-</td>
- </tr>
- </table>
-
- <h3>I. Which Distributions to Include</h3>The following distributions were
- chosen due to their relatively widespread use:
-
- <ul>
- <li>Integer uniform</li>
-
- <li>Floating-point uniform</li>
-
- <li>Exponential</li>
-
- <li>Normal</li>
-
- <li>Gamma</li>
-
- <li>Poisson</li>
-
- <li>Binomial</li>
-
- <li>Geometric</li>
-
- <li>Bernoulli</li>
- </ul>The GNU Scientific Library has a multitude of additional distributions
- that are not mentioned in the table below.
-
- <table border="1" summary="">
- <tr>
- <th>Distribution</th>
-
- <th>this proposal</th>
-
- <th>CLHEP</th>
-
- <th>crng</th>
-
- <th>GNU Scientific Library</th>
-
- <th>Swarm</th>
-
- <th>Numerical Recipes</th>
-
- <th>Knuth</th>
- </tr>
-
- <tr>
- <td>uniform (int)</td>
-
- <td>uniform_int</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>UniformIntegerDist</td>
-
- <td>-</td>
-
- <td>-</td>
- </tr>
-
- <tr>
- <td>uniform (float)</td>
-
- <td>uniform_real</td>
-
- <td>RandFlat</td>
-
- <td>UniformDeviate</td>
-
- <td>flat</td>
-
- <td>UniformDoubleDist</td>
-
- <td>-</td>
-
- <td>uniform</td>
- </tr>
-
- <tr>
- <td>exponential</td>
-
- <td>exponential_distribution</td>
-
- <td>RandExponential</td>
-
- <td>ExponentialDeviate</td>
-
- <td>exponential</td>
-
- <td>ExponentialDist</td>
-
- <td>exponential</td>
-
- <td>exponential</td>
- </tr>
-
- <tr>
- <td>normal</td>
-
- <td>normal_distribution</td>
-
- <td>RandGauss*</td>
-
- <td>NormalDeviate</td>
-
- <td>gaussian</td>
-
- <td>NormalDist</td>
-
- <td>normal (gaussian)</td>
-
- <td>normal</td>
- </tr>
-
- <tr>
- <td>lognormal</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>lognormal</td>
-
- <td>LogNormalDist</td>
-
- <td>-</td>
-
- <td>-</td>
- </tr>
-
- <tr>
- <td>gamma</td>
-
- <td>gamma_distribution</td>
-
- <td>RandGamma</td>
-
- <td>GammaDeviate</td>
-
- <td>gamma</td>
-
- <td>GammaDist</td>
-
- <td>gamma</td>
-
- <td>gamma</td>
- </tr>
-
- <tr>
- <td>beta</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>BetaDeviate</td>
-
- <td>beta</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>beta</td>
- </tr>
-
- <tr>
- <td>poisson</td>
-
- <td>poisson_distribution</td>
-
- <td>Poisson</td>
-
- <td>PoissonDeviate</td>
-
- <td>poisson</td>
-
- <td>PoissonDist</td>
-
- <td>poisson</td>
-
- <td>poisson</td>
- </tr>
-
- <tr>
- <td>binomial</td>
-
- <td>binomial_distribution</td>
-
- <td>RandBinomial</td>
-
- <td>BinomialDeviate</td>
-
- <td>binomial</td>
-
- <td>-</td>
-
- <td>binomial</td>
-
- <td>binomial</td>
- </tr>
-
- <tr>
- <td>geometric</td>
-
- <td>geometric_distribution</td>
-
- <td>-</td>
-
- <td>GeometricDeviate</td>
-
- <td>geometric</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>geometric</td>
- </tr>
-
- <tr>
- <td>bernoulli</td>
-
- <td>bernoulli_distribution</td>
-
- <td>-</td>
-
- <td>BernoulliDeviate</td>
-
- <td>bernoulli</td>
-
- <td>BernoulliDist</td>
-
- <td>-</td>
-
- <td>-</td>
- </tr>
-
- <tr>
- <td>random bit</td>
-
- <td>-</td>
-
- <td>RandBit</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>RandomBitDist</td>
-
- <td>-</td>
-
- <td>-</td>
- </tr>
-
- <tr>
- <td>breit-wigner</td>
-
- <td>-</td>
-
- <td>RandBreitWigner</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>-</td>
- </tr>
-
- <tr>
- <td>chi-square</td>
-
- <td>-</td>
-
- <td>RandChiSquare</td>
-
- <td>-</td>
-
- <td>chisq</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>chi-square</td>
- </tr>
-
- <tr>
- <td>landau</td>
-
- <td>-</td>
-
- <td>Landau</td>
-
- <td>-</td>
-
- <td>landau</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>-</td>
- </tr>
-
- <tr>
- <td>F</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>F</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>F (variance-ratio)</td>
- </tr>
-
- <tr>
- <td>t</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>t</td>
-
- <td>-</td>
-
- <td>-</td>
-
- <td>t</td>
- </tr>
- </table>
-
- <h3>J. Taxonomy of Concepts</h3>All of the engines support the number
- generator requirements, i.e. they are zero-argument function objects which
- return numbers. All of the distributions are one-argument function objects,
- taking a reference to an engine and returning numbers. All of the engines
- and some of the distributions return uniformly distributed random numbers.
- This is reflected in the concept of the uniform random number generator,
- which refines number generator. Engines for pseudo-random numbers model the
- requirements for pseudo-random number engine, which refines uniform random
- number generator.
- <pre>
-NumberGenerator ---- UniformRandomNumberGenerator ---- PseudoRandomNumberGenerator
- \--- RandomDistribution
-</pre>
-
- <h3>K. Validation</h3>How can a user have confidence that the
- implementation of a random-number engine is exactly as specified, correctly
- taking into account any platform pecularities (e.g., odd-sized ints)? After
- all, minor typos in the implementation might not be apparent; the numbers
- produced may look "random". This proposal therefore specifies for each
- engine the 10000th number in the random number sequence that a
- default-constructed engine object produces.
-
- <p>This is considered an important feature for library implementors and
- serious users to check whether the provided library on the given platform
- returns the correct numbers. It could be argued that a library implementor
- should provide a correct implementation of some standard feature in any
- case.</p>
-
- <p>No other library I have encountered provides explicit validation values
- in either their specification or their implementation, although some of
- them claim to be widely portable.</p>
-
- <p>Another design option for validation that was part of early drafts of
- this proposal is moving the reference number (10000th value in the
- sequence) from specification space to implementation space, thus providing
- a <code>validation(x)</code> static member function for each engine that
- compares the hard-coded 10000th value of the sequence with some
- user-provided value <code>x</code> presumeably obtained by actually
- invoking the random-number engine object 10000 times. Due to the
- template-based design, this amounted to a "val" template value parameter
- for each engine, and the <code>validation(x)</code> function reduced to the
- trivial comparison "val == x". Handling validation for floating-point
- engines required more machinery, because template value parameters cannot
- be of floating-point type. Also, from a conceptual perspective, it seemed
- odd to demand a validation decision from the very entitiy which one wanted
- to validate.</p>
-
- <h3>L. Non-Volatile Storage of Engine and Distribution
- State</h3>Pseudo-random number engines and distributions may store their
- state on a <code>std::ostream</code> in textual form and recover it from an
- appropriate <code>std::istream</code>. Each engine specifies how its
- internal state is represented. The specific algorithm of a distribution is
- left implementation-defined, thus no specifics about the representation of
- its internal state are given. A store operation must not affect the number
- sequence produced. It is expected that such external storage happens rarely
- as opposed to producing random numbers, thus no particular attention to
- performance is paid.
-
- <p>Engines and distributions use the usual idioms of
- <code>operator<<</code> and <code>operator>></code>. If the
- user needs additional processing before or after storage on non-volatile
- media, there is always the option to use a temporary
- <code>std::stringstream</code>.</p>
-
- <p>Distributions sometimes store values from their associated source of
- random numbers across calls to their <code>operator()</code>. For example,
- a common method for generating normally distributed random numbers is to
- retrieve two uniformly distributed random numbers and compute two normally
- distributed random numbers out of them. In order to reset the
- distribution's random number cache to a defined state, each distribution
- has a <code>reset</code> member function. It should be called on a
- distribution whenever its associated engine is exchanged or restored.</p>
-
- <h3>M. Values vs. References</h3>Compounded engines such as
- <code>shuffle_output</code> and <code>discard_block</code> contain a base
- engine by value, because compounding is not intended to be used by
- reference to an existing (re-used) engine object.
-
- <p>The wrapper <code>variate_generator</code> can store engines either by
- value or by reference, explicitly chosen by the template parameters. This
- allows to use references to a single engine in several
- <code>variate_generator</code>, but makes it explicit to the user that he
- is responsible for the management of the lifetime of the engine.</p>
-
- <h3>N. Providing the Probability Density Function in Distributions</h3>Some
- libraries provide the probability density function of a given distribution
- as part of that distribution's interface. While this may be useful
- occasionally, this proposal does not provide for such a feature. One reason
- is separation of concerns: The distribution class templates might benefit
- from precomputing large tables of values depending on the distribution
- parameters, while the computation of the probability density function does
- not. Also, the function representation is often straightforward, so the
- user can easily code it himself.
-
- <h3>O. Implementation-defined behaviour</h3>This proposal specifies
- implementation-defined behaviour in a number of places. I believe this is
- unavoidable; this section provides detailed reasoning, including why the
- implementation is required to document the choice.
-
- <p>The precise state-holding base data types for the various engines are
- left implementation-defined, because engines are usually optimized for
- binary integers with 32 bits of word size. The specification in this
- proposal cannot foresee whether a 32 bit quantity on the machine is
- available in C++ as short, int, long, or not at all. It is up to the
- implementation to decide which data type fits best. The implementation is
- required to document the choice of data type, so that users can
- (non-portably) rely on the precise type, for example for further
- computation. Should the ISO C99 extensions become part of ISO C++, the
- implementation-defined types could be replaced by e.g.
- <code>int_least32_t</code>.</p>
-
- <p>The method how to produce non-deterministic random numbers is considered
- implementation-defined, because it inherently depends on the implementation
- and possibly even on the runtime environment: Imagine a platform that has
- operating system support for randomness collection, e.g. from user
- keystrokes and Ethernet inter-packet arrival timing (Linux
- <code>/dev/random</code> does this). If, in some installation, access to
- the operating system functions providing these services has been
- restricted, the C++ non-deterministic random number engine has been
- deprived of its randomness. An implementation is required to document how
- it obtains the non-deterministic random numbers, because only then can
- users' confidence in them grow. Confidence is of particular concern in the
- area of cryptography.</p>
-
- <p>The algorithms how to produce the various distributions are specified as
- implementation-defined, because there is a vast variety of algorithms known
- for each distribution. Each has a different trade-off in terms of speed,
- adaptation to recent computer architectures, and memory use. The
- implementation is required to document its choice so that the user can
- judge whether it is acceptable quality-wise.</p>
-
- <h3>P. Lower and upper bounds on UniformRandomNumberGenerator</h3>The
- member functions <code>min()</code> and <code>max()</code> return the lower
- and upper bounds of a UniformRandomNumberGenerator. This could be a
- random-number engine or one of the <code>uniform_int</code> and
- <code>uniform_real</code> distributions.
-
- <p>Those bounds are not specified to be tight, because for some engines,
- the bounds depend on the seeds. The seed can be changed during the lifetime
- of the engine object, while the values returned by <code>min()</code> and
- <code>max()</code> are invariant. Therefore, <code>min()</code> and
- <code>max()</code> must return conservative bounds that are independent of
- the seed.</p>
-
- <h3>Q. With or without manager class</h3>This proposal presents a design
- with a manager class template, <code>variate_generator</code>, after
- extensive discussion with some members of the computing division of Fermi
- National Accelerator Laboratory. User-written and library-provided engines
- and distributions plug in to the manager class. The approach is remotely
- similar to the locale design in the standard library, where (user-written)
- facets plug in to the (library-provided) locale class.
-
- <p>Earlier versions of this propsoal made (potentially user-written)
- distributions directly visible to (some other) user that wants to get
- random numbers distributed accordingly ("client"), there was no additional
- management layer between the distribution and the client.</p>
-
- <p>The following additional features could be provided by the management
- layer:</p>
-
- <ul>
- <li>The management layer contains an adaptor (to convert the engine's
- output into the distribution's input) in addition to the engine and the
- distribution.</li>
-
- <li>Adaptors and distributions do not store state, but instead, in each
- invocation, consume an arbitrary number of input values and produce a
- fixed number of output values. The management layer is responsible for
- connecting the engine - adaptor - distribution chain, invoking each part
- when more numbers are needed from the next part of the chain.</li>
-
- <li>On request, the management layer is responsible for saving and
- restoring the buffers that exist between engine, adaptor, and
- distribution.</li>
-
- <li>On request, the management layer shares engines with another instance
- of the management layer.</li>
- </ul>It is envisioned that user-written distributions will often be based
- on some arbitrary algorithmic distribution, instead of trying to implement
- a given mathematical probability density function. Here is an example:
-
- <ul>
- <li>Retrieve a uniform integer with value either 1 or 2.</li>
-
- <li>If 1, return a number with normal distribution.</li>
-
- <li>If 2, return a number with gamma distribution.</li>
- </ul>Both in this case and when implementing complex distributions based on
- a probability density function (e.g. the gamma distribution), it is
- important to be able to arbitrarily nest distributions. Either design
- allows for this with utmost ease: Compounding distributions are contained
- in the compound by value, and each one produces a single value on
- invocation. With the alternative design of giving distributions the freedom
- to produce more than one output number in each invocation, compound
- distributions such as the one shown above need to handle the situation that
- each of the compounding members could provide several output values, the
- number of which is unknown at the time the distribution is written.
- (Remember that it is unfeasible to prescribe a precise algorithm for each
- library-provided distribution in the standard, see subsection O.) That
- approach shifts implementation effort from the place where it came up, i.e.
- the distribution that chose to use an algorithm that produces several
- values in one invocation, to the places where that distribution is used.
- This, considered by itself, does not seem to be a good approach. Also, only
- very few distributions lead to a natural implementation that produces
- several values in one invocation; so far, the normal distribution is the
- only one known to me. However, it is expected that there will be plenty of
- distributions that use a normal distribution as its base, so far those
- known to me are lognormal and uniform_on_sphere (both not part of this
- proposal). As a conclusion, independent of whether the design provides for
- a management layer or not, distributions should always return a single
- value on each invocation, and management of buffers for additional values
- that might be produced should be internal to the distribution. Should it
- become necessary for the user to employ buffer management more often, a
- user-written base class for the distributions could be of help.
-
- <p>The ability to share engines is important. This proposal makes lifetime
- management issues explicit by requiring pointer or reference types in the
- template instantiation of <code>variate_generator</code> if reference
- semantics are desired. Without a management class, providing this features
- is much more cumbersome and imposes additional burden on the programmers
- that produce distributions. Alternatively, reference semantics could always
- be used, but this is an error-prone approach due to the lack of a standard
- reference-counted smart pointer. I believe it is impossible to add a
- reference-counted sharing mechanism in a manager-class-free design without
- giving its precise type. And that would certainly conflict in semantic
- scope with a smart pointer that will get into the standard eventually.</p>
-
- <p>The management layer allows for a few common features to be factored
- out, in particular access to the engine and some member typedefs.</p>
-
- <p>Comparison of other differing features between manager and non-manager
- designs:</p>
-
- <ul>
- <li>When passing a <code>variate_generator</code> as a an argument to a
- function, the design in this proposal allows selecting only those
- function signatures during overload resolution that are intended to be
- called with a <code>variate_generator</code>. In contrast, misbehaviour
- is possible without a manager class, similar to iterators in function
- signatures: <code>template<class BiIter> void f(BiIter it)</code>
- matches <code>f(5)</code>, without regard to the bidirectional iterator
- requirements. An error then happens when instantiating f. The situation
- worsens when several competing function templates are available and the
- wrong one is chosen accidentally.</li>
-
- <li>With the engine passed into the distribution's constructor, the full
- type hierarchy of engine (and possibly adaptor) are available to the
- distribution, allowing to cache information derived from the engine (e.g.
- its value range) . Also, (partial) specialization of distributions could
- be written that optimize the interaction with a specific engine and/or
- adaptor. In this proposal's design, this information is available in the
- <code>variate_generator</code> template only. However, optimizations by
- specialization for the engine/adaptor combination are perceived to
- possibly have high benefit, while those for the (engine+adaptor) /
- distribution combination are presumed to be much less beneficial.</li>
-
- <li>Having distribution classes directly exposed to the client easily
- allows that the user writes a distribution with an additional arbitrary
- member function declaration, intended to produce random numbers while
- taking additional parameters into account. In this proposal's design,
- this is possible by using the generic <code>operator()(T x)</code>
- forwarding function.</li>
- </ul>
-
- <h3>R. Add-on packages</h3>This proposal specifies a framework for random
- number generation. Users might have additional requirements not met by this
- framework. The following extensions have been identified, and they are
- expressly not addressed in this proposal. It is perceived that these items
- can be seamlessly implemented in an add-on package which sits on top of an
- implementation according to this proposal.
-
- <ul>
- <li>unique seeding: Make it easy for the user to provide a unique seed
- for each instance of a pseudo-random number engine. Design idea:
- <pre>
- class unique_seed;
-
- template<class Engine>
- Engine seed(unique_seed&);
-</pre>The "seed" function retrieves some unique seed from the unique_seed
-class and then uses the <code>seed(first, last)</code> interface of an engine
-to implant that unique seed. Specific seeding requirements for some engine
-can be met by (partial) template specialization.
- </li>
-
- <li>runtime-replaceable distributions and associated save/restore
- functionality: Provide a class hierarchy that invokes distributions by
- means of a virtual function, thereby allowing for runtime replacement of
- the actual distribution. Provide a factory function to reconstruct the
- distribution instance after saving it to some non-volatile media.</li>
- </ul>
-
- <h3>S. Adaptors</h3>Sometimes, users may want to have better control how
- the bits from the engine are used to fill the mantissa of the
- floating-point value that serves as input to some distribution. This is
- possible by writing an engine wrapper and passing that in to the
- <code>variate_generator</code> as the engine. The
- <code>variate_generator</code> will only apply automatic adaptations if the
- output type of the engine is integers and the input type for the
- distribution is floating-point or vice versa.
-
- <h3>Z. Open issues</h3>
-
- <ul>
- <li>Some engines require non-negative template arguments, usually bit
- counts. Should these be given as "int" or "unsigned int"? Using "unsigned
- int" sometimes adds significant clutter to the presentation. Or "size_t",
- but this is probably too large a type?</li>
- </ul>
-
- <h2>IV. Proposed Text</h2>(Insert the following as a new section in clause
- 26 "Numerics". Adjust the overview at the beginning of clause 26
- accordingly.)
-
- <p>This subclause defines a facility for generating random numbers.</p>
-
- <h3>Random number requirements</h3>A number generator is a function object
- (std:20.3 [lib.function.objects]).
-
- <p>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 (possibly
- <code>const</code>) value of <code>X</code>.</p>
-
- <table border="1" summary="">
- <tr>
- <th colspan="4" align="center">Number generator requirements (in
- addition to function object)</th>
- </tr>
-
- <tr>
- <td>expression</td>
-
- <td>return type</td>
-
- <td>pre/post-condition</td>
-
- <td>complexity</td>
- </tr>
-
- <tr>
- <td><code>X::result_type</code></td>
-
- <td>T</td>
-
- <td><code>std::numeric_limits<T>::is_specialized</code> is
- <code>true</code></td>
-
- <td>compile-time</td>
- </tr>
- </table>
-
- <p>In the following table, <code>X</code> denotes a uniform random number
- generator class returning objects of type <code>T</code>, <code>u</code> is
- a value of <code>X</code> and <code>v</code> is a (possibly
- <code>const</code>) value of <code>X</code>.</p>
-
- <table border="1" summary="">
- <tr>
- <th colspan="4" align="center">Uniform random number generator
- requirements (in addition to number generator)</th>
- </tr>
-
- <tr>
- <td>expression</td>
-
- <td>return type</td>
-
- <td>pre/post-condition</td>
-
- <td>complexity</td>
- </tr>
-
- <tr>
- <td><code>u()</code></td>
-
- <td>T</td>
-
- <td>-</td>
-
- <td>amortized constant</td>
- </tr>
-
- <tr>
- <td><code>v.min()</code></td>
-
- <td><code>T</code></td>
-
- <td>Returns some l where l is less than or equal to all values
- potentially returned by <code>operator()</code>. The return value of
- this function shall not change during the lifetime of
- <code>v</code>.</td>
-
- <td>constant</td>
- </tr>
-
- <tr>
- <td><code>v.max()</code></td>
-
- <td><code>T</code></td>
-
- <td>If <code>std::numeric_limits<T>::is_integer</code>, returns l
- where l is less than or equal to all values potentially returned by
- <code>operator()</code>, otherwise, returns l where l is strictly less
- than all values potentially returned by <code>operator()</code>. In any
- case, the return value of this function shall not change during the
- lifetime of <code>v</code>.</td>
-
- <td>constant</td>
- </tr>
- </table>
-
- <p>In the following table, <code>X</code> denotes a pseudo-random number
- engine class returning objects of type <code>T</code>, <code>t</code> is a
- value of <code>T</code>, <code>u</code> is a value of <code>X</code>,
- <code>v</code> is an lvalue of <code>X</code>, <code>it1</code> is an
- lvalue and <code>it2</code> is a (possibly <code>const</code>) value of an
- input iterator type <code>It</code> having an unsigned integral value type,
- <code>x</code>, <code>y</code> are (possibly <code>const</code>) values of
- <code>X</code>, <code>os</code> is convertible to an lvalue of type
- <code>std::ostream</code>, and <code>is</code> is convertible to an lvalue
- of type <code>std::istream</code>.</p>
-
- <p>A pseudo-random number engine x has a state x(i) at any given time. The
- specification of each pseudo-random number engines defines the size of its
- state in multiples of the size of its <code>result_type</code>, given as an
- integral constant expression.</p>
-
- <table border="1" summary="">
- <tr>
- <th colspan="4" align="center">Pseudo-random number engine requirements
- (in addition to uniform random 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()</code></td>
-
- <td>-</td>
-
- <td>creates an engine with the same initial state as all other
- default-constructed engines of type <code>X</code> in the program.</td>
-
- <td>O(size of state)</td>
- </tr>
-
- <tr>
- <td><code>X(it1, it2)</code></td>
-
- <td>-</td>
-
- <td>creates an engine with the initial state given by the range
- <code>[it1,it2)</code>. <code>it1</code> is advanced by the size of
- state. If the size of the range [it1,it2) is insufficient, leaves
- <code>it1 == it2</code> and throws <code>invalid_argument</code>.</td>
-
- <td>O(size of state)</td>
- </tr>
-
- <tr>
- <td><code>u.seed()</code></td>
-
- <td>void</td>
-
- <td>post: <code>u == X()</code></td>
-
- <td>O(size of state)</td>
- </tr>
-
- <tr>
- <td><code>u.seed(it1, it2)</code></td>
-
- <td>void</td>
-
- <td>post: If there are sufficiently many values in [it1, it2) to
- initialize the state of <code>u</code>, then <code>u ==
- X(it1,it2)</code>. Otherwise, <code>it1 == it2</code>, throws
- <code>invalid_argument</code>, and further use of <code>u</code>
- (except destruction) is undefined until a <code>seed</code> member
- function has been executed without throwing an exception.</td>
-
- <td>O(size of state)</td>
- </tr>
-
- <tr>
- <td><code>u()</code></td>
-
- <td><code>T</code></td>
-
- <td>given the state u(i) of the engine, computes u(i+1), sets the state
- to u(i+1), and returns some output dependent on u(i+1)</td>
-
- <td>amortized constant</td>
- </tr>
-
- <tr>
- <td><code>x == y</code></td>
-
- <td><code>bool</code></td>
-
- <td><code>==</code> is an equivalence relation. The current state x(i)
- of x is equal to the current state y(j) of y.</td>
-
- <td>O(size of state)</td>
- </tr>
-
- <tr>
- <td><code>x != y</code></td>
-
- <td><code>bool</code></td>
-
- <td><code>!(x == y)</code></td>
-
- <td>O(size of state)</td>
- </tr>
-
- <tr>
- <td><code>os << x</code></td>
-
- <td><code>std::ostream&</code></td>
-
- <td>writes the textual representation of the state x(i) of
- <code>x</code> to <code>os</code>, with
- <code>os.<em>fmtflags</em></code> set to
- <code>ios_base::dec|ios_base::fixed|ios_base::left</code> and the fill
- character set to the space character. In the output, adjacent numbers
- are separated by one or more space characters.<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 >> v</code></td>
-
- <td><code>std::istream&</code></td>
-
- <td>sets the state v(i) of <code>v</code> as determined by reading its
- textual representation from <code>is</code>.<br>
- post: The <code>is.<em>fmtflags</em></code> are unchanged.</td>
-
- <td>O(size of state)</td>
- </tr>
- </table>
-
- <p>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" summary="">
- <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>
-
- <p>In the following subclauses, a template parameter named
- <code>UniformRandomNumberGenerator</code> shall denote a class that
- satisfies all the requirements of a uniform random number generator.
- Moreover, a template parameter named <code>Distribution</code> shall denote
- a type that satisfies all the requirements of a random distribution.
- Furthermore, a template parameter named <code>RealType</code> shall denote
- a type that holds an approximation to a real number. This type shall meet
- the requirements for a numeric type (26.1 [lib.numeric.requirements]), the
- binary operators +, -, *, / shall be applicable to it, a conversion from
- <code>double</code> shall exist, and function signatures corresponding to
- those for type <code>double</code> in subclause 26.5 [lib.c.math] shall be
- available by argument-dependent lookup (3.4.2 [basic.lookup.koenig]).
- <em>[Note: The built-in floating-point types <code>float</code> and
- <code>double</code> meet these requirements.]</em></p>
-
- <h3>Header <code><random></code> synopsis</h3>
- <pre>
-namespace std {
- template<class UniformRandomNumberGenerator, class Distribution>
- class variate_generator;
-
- template<class IntType, IntType a, IntType c, IntType m>
- class linear_congruential;
-
- template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
- int s, UIntType b, int t, UIntType c, int l>
- class mersenne_twister;
-
- template<class IntType, IntType m, int s, int r>
- class subtract_with_carry;
-
- template<class RealType, int w, int s, int r>
- class subtract_with_carry_01;
-
- template<class UniformRandomNumberGenerator, int p, int r>
- class discard_block;
-
- template<class UniformRandomNumberGenerator1, int s1,
- class UniformRandomNumberGenerator2, int s2>
- class xor_combine;
-
- class random_device;
-
- template<class IntType = int>
- class uniform_int;
-
- template<class RealType = double>
- class bernoulli_distribution;
-
- template<class IntType = int, class RealType = double>
- class geometric_distribution;
-
- template<class IntType = int, class RealType = double>
- class poisson_distribution;
-
- template<class IntType = int, class RealType = double>
- class binomial_distribution;
-
- template<class RealType = double>
- class uniform_real;
-
- template<class RealType = double>
- class exponential_distribution;
-
- template<class RealType = double>
- class normal_distribution;
-
- template<class RealType = double>
- class gamma_distribution;
-
-} // namespace std
-</pre>
-
- <h3>Class template <code>variate_generator</code></h3>A
- <code>variate_generator</code> produces random numbers, drawing randomness
- from an underlying uniform random number generator and shaping the
- distribution of the numbers corresponding to a distribution function.
- <pre>
-template<class Engine, class Distribution>
-class variate_generator
-{
-public:
- typedef Engine engine_type;
- typedef /* <em>implementation defined</em> */ engine_value_type;
- typedef Distribution distribution_type;
- typedef typename Distribution::result_type result_type;
-
- variate_generator(engine_type eng, distribution_type d);
-
- result_type operator()();
- template<class T> result_type operator()(T value);
-
- engine_value_type& engine();
- const engine_value_type& engine() const;
-
- distribution_type& distribution();
- const distribution_type& distribution() const;
-
- result_type min() const;
- result_type max() const;
-};
-</pre>The template argument for the parameter <code>Engine</code> shall be of
-the form <code><em>U</em></code>, <code><em>U</em>&</code>, or <code><em>
- U</em>*</code>, where <code><em>U</em></code> denotes a class that
- satisfies all the requirements of a uniform random number generator. The
- member <code>engine_value_type</code> shall name <code><em>U</em></code>.
-
- <p>Specializations of <code>variate_generator</code> satisfy the
- requirements of CopyConstructible. They also satisfy the requirements of
- Assignable unless the template parameter <code>Engine</code> is of the form
- <code><em>U</em>&</code>.</p>
-
- <p>The complexity of all functions specified in this section is constant.
- No function described in this section except the constructor throws an
- exception.</p>
- <pre>
- variate_generator(engine_type eng, distribution_type d)
-</pre><strong>Effects:</strong> Constructs a <code>variate_generator</code>
-object with the associated uniform random number generator <code>eng</code>
-and the associated random distribution <code>d</code>.<br>
- <strong>Throws:</strong> If and what the copy constructor of Engine or
- Distribution throws.
- <pre>
- result_type operator()()
-</pre><strong>Returns:</strong> <code>distribution()(e)</code><br>
- <strong>Notes:</strong> The sequence of numbers produced by the uniform
- random number generator <code>e</code>, s<sub>e</sub>, is obtained from the
- sequence of numbers produced by the associated uniform random number
- generator <code>eng</code>, s<sub>eng</sub>, as follows: Consider the
- values of <code>numeric_limits<<em>T</em>>::is_integer</code> for
- <code><em>T</em></code> both <code>Distribution::input_type</code> and
- <code>engine_value_type::result_type</code>. If the values for both types
- are <code>true</code>, then s<sub>e</sub> is identical to s<sub>eng</sub>.
- Otherwise, if the values for both types are <code>false</code>, then the
- numbers in s<sub>eng</sub> are divided by
- <code>engine().max()-engine().min()</code> to obtain the numbers in
- s<sub>e</sub>. Otherwise, if the value for
- <code>engine_value_type::result_type</code> is <code>true</code> and the
- value for <code>Distribution::input_type</code> is <code>false</code>, then
- the numbers in s<sub>eng</sub> are divided by
- <code>engine().max()-engine().min()+1</code> to obtain the numbers in
- s<sub>e</sub>. Otherwise, the mapping from s<sub>eng</sub> to s<sub>e</sub>
- is implementation-defined. In all cases, an implicit conversion from
- <code>engine_value_type::result_type</code> to
- <code>Distribution::input_type</code> is performed. If such a conversion
- does not exist, the program is ill-formed.
- <pre>
- template<class T> result_type operator()(T value)
-</pre><strong>Returns:</strong> <code>distribution()(e, value)</code>. For
-the semantics of <code>e</code>, see the description of
-<code>operator()()</code>.
- <pre>
- engine_value_type& engine()
-</pre><strong>Returns:</strong> A reference to the associated uniform random
-number generator.
- <pre>
- const engine_value_type& engine() const
-</pre><strong>Returns:</strong> A reference to the associated uniform random
-number generator.
- <pre>
- distribution_type& distribution()
-</pre><strong>Returns:</strong> A reference to the associated random
-distribution.
- <pre>
- const distribution_type& distribution() const
-</pre><strong>Returns:</strong> A reference to the associated random
-distribution.
- <pre>
- result_type min() const
-</pre><strong>Precondition:</strong> <code>distribution().min()</code> is
-well-formed<br>
- <strong>Returns:</strong> <code>distribution().min()</code>
- <pre>
- result_type max() const
-</pre><strong>Precondition:</strong> <code>distribution().max()</code> is
-well-formed<br>
- <strong>Returns:</strong> <code>distribution().max()</code>
-
- <h3>Random number engine class templates</h3>Except where specified
- otherwise, the complexity of all functions specified in the following
- sections is constant. No function described in this section except the
- constructor and seed functions taking an iterator range [it1,it2) throws an
- exception.
-
- <p>The class templates specified in this section satisfy all the
- requirements of a pseudo-random number engine (given in tables in section
- x.x), except where specified otherwise. Descriptions are provided here only
- for operations on the engines that are not described in one of these tables
- or for operations where there is additional semantic information.</p>
-
- <p>All members declared <code>static const</code> in any of the following
- class templates shall be defined in such a way that they are usable as
- integral constant expressions.</p>
-
- <h4>Class template <code>linear_congruential</code></h4>A
- <code>linear_congruential</code> engine produces random numbers using a
- linear function x(i+1) := (a * x(i) + c) mod m.
- <pre>
-namespace std {
- template<class IntType, IntType a, IntType c, IntType m>
- class linear_congruential
- {
- public:
- // <em>types</em>
- typedef IntType result_type;
-
- // <em>parameter values</em>
- static const IntType multiplier = a;
- static const IntType increment = c;
- static const IntType modulus = m;
-
- // <em> constructors and member function</em>
- explicit linear_congruential(IntType x0 = 1);
- template<class In> linear_congruential(In& first, In last);
- void seed(IntType x0 = 1);
- template<class In> void seed(In& first, In last);
- result_type min() const;
- result_type max() const;
- result_type operator()();
- };
-
- template<class IntType, IntType a, IntType c, IntType m>
- bool operator==(const linear_congruential<IntType, a, c, m>& x,
- const linear_congruential<IntType, a, c, m>& y);
- template<class IntType, IntType a, IntType c, IntType m>
- bool operator!=(const linear_congruential<IntType, a, c, m>& x,
- const linear_congruential<IntType, a, c, m>& y);
-
- template<class CharT, class traits,
- class IntType, IntType a, IntType c, IntType m>
- basic_ostream<CharT, traits>& operator<<(basic_ostream<CharT, traits>& os,
- const linear_congruential<IntType, a, c, m>& x);
- template<class CharT, class traits,
- class IntType, IntType a, IntType c, IntType m>
- basic_istream<CharT, traits>& operator>>(basic_istream<CharT, traits>& is,
- linear_congruential<IntType, a, c, m>& x);
-}
-</pre>The template parameter <code>IntType</code> shall denote an integral
-type large enough to store values up to (m-1). If the template parameter
-<code>m</code> is 0, the behaviour is implementation-defined. Otherwise, the
-template parameters <code>a</code> and <code>c</code> shall be less than m.
-
- <p>The size of the state x(i) is 1.</p>
- <pre>
- explicit linear_congruential(IntType x0 = 1)
-</pre><strong>Requires:</strong> <code>c > 0 || (x0 % m) > 0</code><br>
-
- <strong>Effects:</strong> Constructs a <code>linear_congruential</code>
- engine with state x(0) := <code>x0</code> mod m.
- <pre>
- void seed(IntType x0 = 1)
-</pre><strong>Requires:</strong> <code>c > 0 || (x0 % m) > 0</code><br>
-
- <strong>Effects:</strong> Sets the state x(i) of the engine to
- <code>x0</code> mod m.
- <pre>
- template<class In> linear_congruential(In& first, In last)
-</pre><strong>Requires:</strong> <code>c > 0 || *first > 0</code><br>
- <strong>Effects:</strong> Sets the state x(i) of the engine to
- <code>*first</code> mod m.<br>
- <strong>Complexity:</strong> Exactly one dereference of
- <code>*first</code>.
- <pre>
- template<class CharT, class traits,
- class IntType, IntType a, IntType c, IntType m>
- basic_ostream<CharT, traits>& operator<<(basic_ostream<CharT, traits>& os,
- const linear_congruential<IntType, a, c, m>& x);
-</pre><strong>Effects:</strong> Writes x(i) to <code>os</code>.
-
- <h4>Class template <code>mersenne_twister</code></h4>A
- <code>mersenne_twister</code> engine produces random numbers o(x(i)) using
- the following computation, performed modulo 2<sup>w</sup>. <code>um</code>
- is a value with only the upper <code>w-r</code> bits set in its binary
- representation. <code>lm</code> is a value with only its lower
- <code>r</code> bits set in its binary representation. <em>rshift</em> is a
- bitwise right shift with zero-valued bits appearing in the high bits of the
- result. <em>lshift</em> is a bitwise left shift with zero-valued bits
- appearing in the low bits of the result.
-
- <ul>
- <li>y(i) = (x(i-n) <em>bitand</em> um) | (x(i-(n-1)) <em>bitand</em>
- lm)</li>
-
- <li>If the lowest bit of the binary representation of y(i) is set, x(i) =
- x(i-(n-m)) <em>xor</em> (y(i) <em>rshift</em> 1) <em>xor</em> a;
- otherwise x(i) = x(i-(n-m)) <em>xor</em> (y(i) <em>rshift</em> 1).</li>
-
- <li>z1(i) = x(i) <em>xor</em> ( x(i) <em>rshift</em> u )</li>
-
- <li>z2(i) = z1(i) <em>xor</em> ( (z1(i) <em>lshift</em> s)
- <em>bitand</em> b )</li>
-
- <li>z3(i) = z2(i) <em>xor</em> ( (z2(i) <em>lshift</em> t)
- <em>bitand</em> c )</li>
-
- <li>o(x(i)) = z3(i) <em>xor</em> ( z3(i) <em>rshift</em> l )</li>
- </ul>
- <pre>
-namespace std {
- template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
- int s, UIntType b, int t, UIntType c, int l>
- class mersenne_twister
- {
- public:
- // <em>types</em>
- typedef UIntType result_type;
-
- // <em>parameter values</em>
- static const int word_size = w;
- static const int state_size = n;
- static const int shift_size = m;
- static const int mask_bits = r;
- static const UIntType parameter_a = a;
- static const int output_u = u;
- static const int output_s = s;
- static const UIntType output_b = b;
- static const int output_t = t;
- static const UIntType output_c = c;
- static const int output_l = l;
-
- // <em> constructors and member function</em>
- mersenne_twister();
- explicit mersenne_twister(UIntType value);
- template<class In> mersenne_twister(In& first, In last);
- void seed();
- void seed(UIntType value);
- template<class In> void seed(In& first, In last);
- result_type min() const;
- result_type max() const;
- result_type operator()();
- };
-
- template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
- int s, UIntType b, int t, UIntType c, int l>
- bool operator==(const mersenne_twister<UIntType, w, n, m, r, a, u, s, b, t, c, l>& y,
- const mersenne_twister<UIntType, w, n, m, r, a, u, s, b, t, c, l>& x);
- template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
- int s, UIntType b, int t, UIntType c, int l>
- bool operator!=(const mersenne_twister<UIntType, w, n, m, r, a, u, s, b, t, c, l>& y,
- const mersenne_twister<UIntType, w, n, m, r, a, u, s, b, t, c, l>& x);
-
- template<class CharT, class traits,
- class UIntType, int w, int n, int m, int r, UIntType a, int u,
- int s, UIntType b, int t, UIntType c, int l>
- basic_ostream<CharT, traits>& operator<<(basic_ostream<CharT, traits>& os,
- const mersenne_twister<UIntType, w, n, m, r, a, u, s, b, t, c, l>& x);
- template<class CharT, class traits,
- class UIntType, int w, int n, int m, int r, UIntType a, int u,
- int s, UIntType b, int t, UIntType c, int l>
- basic_istream<CharT, traits>& operator>>(basic_istream<CharT, traits>& is,
- mersenne_twister<UIntType, w, n, m, r, a, u, s, b, t, c, l>& x);
-}
-</pre>The template parameter <code>UIntType</code> shall denote an unsigned
-integral type large enough to store values up to 2<sup>w</sup>-1. Also, the
-following relations shall hold: 1<=m<=n. 0<=r,u,s,t,l<=w.
-0<=a,b,c<=2<sup>w</sup>-1.
-
- <p>The size of the state x(i) is <code>n</code>.</p>
- <pre>
- mersenne_twister()
-</pre><strong>Effects:</strong> Constructs a <code>mersenne_twister</code>
-engine and invokes <code>seed()</code>.
- <pre>
- explicit mersenne_twister(result_type value)
-</pre><strong>Effects:</strong> Constructs a <code>mersenne_twister</code>
-engine and invokes <code>seed(value)</code>.
- <pre>
- template<class In> mersenne_twister(In& first, In last)
-</pre><strong>Effects:</strong> Constructs a <code>mersenne_twister</code>
-engine and invokes <code>seed(first, last)</code>.
- <pre>
- void seed()
-</pre><strong>Effects:</strong> Invokes <code>seed(4357)</code>.
- <pre>
- void seed(result_type value)
-</pre><strong>Requires:</strong> <code>value > 0</code><br>
- <strong>Effects:</strong> With a linear congruential generator l(i) having
- parameters m<sub>l</sub> = 2<sup>32</sup>, a<sub>l</sub> = 69069,
- c<sub>l</sub> = 0, and l(0) = <code>value</code>, sets x(-n) ... x(-1) to
- l(1) ... l(n), respectively.<br>
- <strong>Complexity:</strong> O(n)
- <pre>
- template<class In> void seed(In& first, In last)
-</pre><strong>Effects:</strong> Given the values z<sub>0</sub> ...
-z<sub>n-1</sub> obtained by dereferencing [first, first+n), sets x(-n) ...
-x(-1) to z<sub>0</sub> mod 2<sup>w</sup> ... z<sub>n-1</sub> mod
-2<sup>w</sup>.<br>
- <strong>Complexity:</strong> Exactly <code>n</code> dereferences of
- <code>first</code>.
- <pre>
- template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
- int s, UIntType b, int t, UIntType c, int l>
- bool operator==(const mersenne_twister<UIntType, w, n, m, r, a, u, s, b, t, c, l>& y,
- const mersenne_twister<UIntType, w, n, m, r, a, u, s, b, t, c, l>& x)
-</pre><strong>Returns:</strong> x(i-n) == y(j-n) and ... and x(i-1) ==
-y(j-1)<br>
- <strong>Notes:</strong> Assumes the next output of <code>x</code> is
- o(x(i)) and the next output of <code>y</code> is o(y(j)).<br>
- <strong>Complexity:</strong> O(n)
- <pre>
- template<class CharT, class traits,
- class UIntType, int w, int n, int m, int r, UIntType a, int u,
- int s, UIntType b, int t, UIntType c, int l>
- basic_ostream<CharT, traits>& operator<<(basic_ostream<CharT, traits>& os,
- const mersenne_twister<UIntType, w, n, m, r, a, u, s, b, t, c, l>& x)
-</pre><strong>Effects:</strong> Writes x(i-n), ... x(i-1) to <code>os</code>,
-in that order.<br>
- <strong>Complexity:</strong> O(n)
-
- <h4>Class template <code>subtract_with_carry</code></h4>A
- <code>subtract_with_carry</code> engine produces integer random numbers
- using x(i) = (x(i-s) - x(i-r) - carry(i-1)) mod m; carry(i) = 1 if x(i-s) -
- x(i-r) - carry(i-1) < 0, else carry(i) = 0.
- <pre>
-namespace std {
- template<class IntType, IntType m, int s, int r>
- class subtract_with_carry
- {
- public:
- // <em>types</em>
- typedef IntType result_type;
-
- // <em>parameter values</em>
- static const IntType modulus = m;
- static const int long_lag = r;
- static const int short_lag = s;
-
- // <em> constructors and member function</em>
- subtract_with_carry();
- explicit subtract_with_carry(IntType value);
- template<class In> subtract_with_carry(In& first, In last);
- void seed(IntType value = 19780503);
- template<class In> void seed(In& first, In last);
- result_type min() const;
- result_type max() const;
- result_type operator()();
- };
- template<class IntType, IntType m, int s, int r>
- bool operator==(const subtract_with_carry<IntType, m, s, r> & x,
- const subtract_with_carry<IntType, m, s, r> & y);
-
- template<class IntType, IntType m, int s, int r>
- bool operator!=(const subtract_with_carry<IntType, m, s, r> & x,
- const subtract_with_carry<IntType, m, s, r> & y);
-
- template<class CharT, class Traits,
- class IntType, IntType m, int s, int r>
- std::basic_ostream<CharT,Traits>& operator<<(std::basic_ostream<CharT,Traits>& os,
- const subtract_with_carry<IntType, m, s, r>& f);
-
- template<class CharT, class Traits,
- class IntType, IntType m, int s, int r>
- std::basic_istream<CharT,Traits>& operator>>(std::basic_istream<CharT,Traits>& is,
- subtract_with_carry<IntType, m, s, r>& f);
-}
-</pre>The template parameter <code>IntType</code> shall denote a signed
-integral type large enough to store values up to m-1. The following relation
-shall hold: 0<s<r. Let w the number of bits in the binary
-representation of m.
-
- <p>The size of the state is <code>r</code>.</p>
- <pre>
- subtract_with_carry()
-</pre><strong>Effects:</strong> Constructs a <code>subtract_with_carry</code>
-engine and invokes <code>seed()</code>.
- <pre>
- explicit subtract_with_carry(IntType value)
-</pre><strong>Effects:</strong> Constructs a <code>subtract_with_carry</code>
-engine and invokes <code>seed(value)</code>.
- <pre>
- template<class In> subtract_with_carry(In& first, In last)
-</pre><strong>Effects:</strong> Constructs a <code>subtract_with_carry</code>
-engine and invokes <code>seed(first, last)</code>.
- <pre>
- void seed(IntType value = 19780503)
-</pre><strong>Requires:</strong> <code>value > 0</code><br>
- <strong>Effects:</strong> With a linear congruential generator l(i) having
- parameters m<sub>l</sub> = 2147483563, a<sub>l</sub> = 40014, c<sub>l</sub>
- = 0, and l(0) = <code>value</code>, sets x(-r) ... x(-1) to l(1) mod m ...
- l(r) mod m, respectively. If x(-1) == 0, sets carry(-1) = 1, else sets
- carry(-1) = 0.<br>
- <strong>Complexity:</strong> O(r)
- <pre>
- template<class In> void seed(In& first, In last)
-</pre><strong>Effects:</strong> With n=w/32+1 (rounded downward) and given
-the values z<sub>0</sub> ... z<sub>n*r-1</sub> obtained by dereferencing
-[first, first+n*r), sets x(-r) ... x(-1) to (z<sub>0</sub> * 2<sup>32</sup> +
-... + z<sub>n-1</sub> * 2<sup>32*(n-1)</sup>) mod m ... (z<sub>(r-1)*n</sub>
-* 2<sup>32</sup> + ... + z<sub>r-1</sub> * 2<sup>32*(n-1)</sup>) mod m. If
-x(-1) == 0, sets carry(-1) = 1, else sets carry(-1) = 0.<br>
- <strong>Complexity:</strong> Exactly <code>r*n</code> dereferences of
- <code>first</code>.
- <pre>
- template<class IntType, IntType m, int s, int r>
- bool operator==(const subtract_with_carry<IntType, m, s, r> & x,
- const subtract_with_carry<IntType, m, s, r> & y)
-</pre><strong>Returns:</strong> x(i-r) == y(j-r) and ... and x(i-1) ==
-y(j-1).<br>
- <strong>Notes:</strong> Assumes the next output of <code>x</code> is x(i)
- and the next output of <code>y</code> is y(j).<br>
- <strong>Complexity:</strong> O(r)
- <pre>
- template<class CharT, class Traits,
- class IntType, IntType m, int s, int r>
- std::basic_ostream<CharT,Traits>& operator<<(std::basic_ostream<CharT,Traits>& os,
- const subtract_with_carry<IntType, m, s, r>& f)
-</pre><strong>Effects:</strong> Writes x(i-r) ... x(i-1), carry(i-1) to
-<code>os</code>, in that order.<br>
- <strong>Complexity:</strong> O(r)
-
- <h4>Class template <code>subtract_with_carry_01</code></h4>A
- <code>subtract_with_carry_01</code> engine produces floating-point random
- numbers using x(i) = (x(i-s) - x(i-r) - carry(i-1)) mod 1; carry(i) =
- 2<sup>-w</sup> if x(i-s) - x(i-r) - carry(i-1) < 0, else carry(i) = 0.
- <pre>
-namespace std {
- template<class RealType, int w, int s, int r>
- class subtract_with_carry_01
- {
- public:
- // <em>types</em>
- typedef RealType result_type;
-
- // <em>parameter values</em>
- static const int word_size = w;
- static const int long_lag = r;
- static const int short_lag = s;
-
- // <em> constructors and member function</em>
- subtract_with_carry_01();
- explicit subtract_with_carry_01(unsigned int value);
- template<class In> subtract_with_carry_01(In& first, In last);
- void seed(unsigned int value = 19780503);
- template<class In> void seed(In& first, In last);
- result_type min() const;
- result_type max() const;
- result_type operator()();
- };
- template<class RealType, int w, int s, int r>
- bool operator==(const subtract_with_carry_01<RealType, w, s, r> x,
- const subtract_with_carry_01<RealType, w, s, r> y);
-
- template<class RealType, int w, int s, int r>
- bool operator!=(const subtract_with_carry_01<RealType, w, s, r> x,
- const subtract_with_carry_01<RealType, w, s, r> y);
-
- template<class CharT, class Traits,
- class RealType, int w, int s, int r>
- std::basic_ostream<CharT,Traits>& operator<<(std::basic_ostream<CharT,Traits>& os,
- const subtract_with_carry_01<RealType, w, s, r>& f);
-
- template<class CharT, class Traits,
- class RealType, int w, int s, int r>
- std::basic_istream<CharT,Traits>& operator>>(std::basic_istream<CharT,Traits>& is,
- subtract_with_carry_01<RealType, w, s, r>& f);
-}
-</pre>The following relation shall hold: 0<s<r.
-
- <p>The size of the state is <code>r</code>.</p>
- <pre>
- subtract_with_carry_01()
-</pre><strong>Effects:</strong> Constructs a
-<code>subtract_with_carry_01</code> engine and invokes <code>seed()</code>.
- <pre>
- explicit subtract_with_carry_01(unsigned int value)
-</pre><strong>Effects:</strong> Constructs a
-<code>subtract_with_carry_01</code> engine and invokes
-<code>seed(value)</code>.
- <pre>
- template<class In> subtract_with_carry_01(In& first, In last)
-</pre><strong>Effects:</strong> Constructs a
-<code>subtract_with_carry_01</code> engine and invokes <code>seed(first,
-last)</code>.
- <pre>
- void seed(unsigned int value = 19780503)
-</pre><strong>Effects:</strong> With a linear congruential generator l(i)
-having parameters m = 2147483563, a = 40014, c = 0, and l(0) =
-<code>value</code>, sets x(-r) ... x(-1) to (l(1)*2<sup>-w</sup>) mod 1 ...
-(l(r)*2<sup>-w</sup>) mod 1, respectively. If x(-1) == 0, sets carry(-1) =
-2<sup>-w</sup>, else sets carry(-1) = 0.<br>
- <strong>Complexity:</strong> O(r)
- <pre>
- template<class In> void seed(In& first, In last)
-</pre><strong>Effects:</strong> With n=w/32+1 (rounded downward) and given
-the values z<sub>0</sub> ... z<sub>n*r-1</sub> obtained by dereferencing
-[first, first+n*r), sets x(-r) ... x(-1) to (z<sub>0</sub> * 2<sup>32</sup> +
-... + z<sub>n-1</sub> * 2<sup>32*(n-1)</sup>) * 2<sup>-w</sup> mod 1 ...
-(z<sub>(r-1)*n</sub> * 2<sup>32</sup> + ... + z<sub>r-1</sub> *
-2<sup>32*(n-1)</sup>) * 2<sup>-w</sup> mod 1. If x(-1) == 0, sets carry(-1) =
-2<sup>-w</sup>, else sets carry(-1) = 0.<br>
- <strong>Complexity:</strong> O(r*n)
- <pre>
- template<class RealType, int w, int s, int r>
- bool operator==(const subtract_with_carry<RealType, w, s, r> x,
- const subtract_with_carry<RealType, w, s, r> y);
-</pre><strong>Returns:</strong> true, if and only if x(i-r) == y(j-r) and ...
-and x(i-1) == y(j-1).<br>
- <strong>Complexity:</strong> O(r)
- <pre>
- template<class CharT, class Traits,
- class RealType, int w, int s, int r>
- std::basic_ostream<CharT,Traits>& operator<<(std::basic_ostream<CharT,Traits>& os,
- const subtract_with_carry<RealType, w, s, r>& f);
-</pre><strong>Effects:</strong> Write x(i-r)*2<sup>w</sup> ...
-x(i-1)*2<sup>w</sup>, carry(i-1)*2<sup>w</sup> to <code>os</code>, in that
-order.<br>
- <strong>Complexity:</strong> O(r)
-
- <h4>Class template <code>discard_block</code></h4>A
- <code>discard_block</code> engine produces random numbers from some base
- engine by discarding blocks of data.
- <pre>
-namespace std {
- template<class UniformRandomNumberGenerator, int p, int r>
- class discard_block
- {
- public:
- // <em>types</em>
- typedef UniformRandomNumberGenerator base_type;
- typedef typename base_type::result_type result_type;
-
- // <em>parameter values</em>
- static const int block_size = p;
- static const int used_block = r;
-
- // <em> constructors and member function</em>
- discard_block();
- explicit discard_block(const base_type & rng);
- template<class In> discard_block(In& first, In last);
- void seed();
- template<class In> void seed(In& first, In last);
- const base_type& base() const;
- result_type min() const;
- result_type max() const;
- result_type operator()();
- private:
- // base_type b; <em>exposition only</em>
- // int n; <em>exposition only</em>
- };
- template<class UniformRandomNumberGenerator, int p, int r>
- bool operator==(const discard_block<UniformRandomNumberGenerator,p,r> & x,
- (const discard_block<UniformRandomNumberGenerator,p,r> & y);
- template<class UniformRandomNumberGenerator, int p, int r,
- typename UniformRandomNumberGenerator::result_type val>
- bool operator!=(const discard_block<UniformRandomNumberGenerator,p,r> & x,
- (const discard_block<UniformRandomNumberGenerator,p,r> & y);
-
- template<class CharT, class traits,
- class UniformRandomNumberGenerator, int p, int r>
- basic_ostream<CharT, traits>& operator<<(basic_ostream<CharT, traits>& os,
- const discard_block<UniformRandomNumberGenerator,p,r> & x);
- template<class CharT, class traits,
- class UniformRandomNumberGenerator, int p, int r>
- basic_istream<CharT, traits>& operator>>(basic_istream<CharT, traits>& is,
- discard_block<UniformRandomNumberGenerator,p,r> & x);
-
-}
-</pre>The template parameter <code>UniformRandomNumberGenerator</code> shall
-denote a class that satisfies all the requirements of a uniform random number
-generator, given in tables in section x.x. r <= p. The size of the state
-is the size of <code><em>b</em></code> plus 1.
- <pre>
- discard_block()
-</pre><strong>Effects:</strong> Constructs a <code>discard_block</code>
-engine. To construct the subobject <em>b</em>, invokes its default
-constructor. Sets <code>n = 0</code>.
- <pre>
- explicit discard_block(const base_type & rng)
-</pre><strong>Effects:</strong> Constructs a <code>discard_block</code>
-engine. Initializes <em>b</em> with a copy of <code>rng</code>. Sets <code>n
-= 0</code>.
- <pre>
- template<class In> discard_block(In& first, In last)
-</pre><strong>Effects:</strong> Constructs a <code>discard_block</code>
-engine. To construct the subobject <em>b</em>, invokes the <code>b(first,
-last)</code> constructor. Sets <code>n = 0</code>.
- <pre>
- void seed()
-</pre><strong>Effects:</strong> Invokes <code><em>b</em>.seed()</code> and
-sets <code>n = 0</code>.
- <pre>
- template<class In> void seed(In& first, In last)
-</pre><strong>Effects:</strong> Invokes <code><em>b</em>.seed(first,
-last)</code> and sets <code>n = 0</code>.
- <pre>
- const base_type& base() const
-</pre><strong>Returns:</strong> <em>b</em>
- <pre>
- result_type operator()()
-</pre><strong>Effects:</strong> If <em>n</em> >= r, invokes
-<code><em>b</em></code> (p-r) times, discards the values returned, and sets
-<code>n = 0</code>. In any case, then increments <code>n</code> and returns
-<code><em>b()</em></code>.
- <pre>
- template<class CharT, class traits,
- class UniformRandomNumberGenerator, int p, int r>
- basic_ostream<CharT, traits>& operator<<(basic_ostream<CharT, traits>& os,
- const discard_block<UniformRandomNumberGenerator,p,r> & x);
-</pre><strong>Effects:</strong> Writes <code><em>b</em></code>, then
-<code><em>n</em></code> to <code>os</code>.
-
- <h4>Class template <code>xor_combine</code></h4>A <code>xor_combine</code>
- engine produces random numbers from two integer base engines by merging
- their random values with bitwise exclusive-or.
- <pre>
-namespace std {
- template<class UniformRandomNumberGenerator1, int s1,
- class UniformRandomNumberGenerator2, int s2>
- class xor_combine
- {
- public:
- // <em>types</em>
- typedef UniformRandomNumberGenerator1 base1_type;
- typedef UniformRandomNumberGenerator2 base2_type;
- typedef typename base_type::result_type result_type;
-
- // <em>parameter values</em>
- static const int shift1 = s1;
- static const int shift2 = s2;
-
- // <em> constructors and member function</em>
- xor_combine();
- xor_combine(const base1_type & rng1, const base2_type & rng2);
- template<class In> xor_combine(In& first, In last);
- void seed();
- template<class In> void seed(In& first, In last);
- const base1_type& base1() const;
- const base2_type& base2() const;
- result_type min() const;
- result_type max() const;
- result_type operator()();
- private:
- // base1_type b1; <em>exposition only</em>
- // base2_type b2; <em>exposition only</em>
- };
- template<class UniformRandomNumberGenerator1, int s1,
- class UniformRandomNumberGenerator2, int s2>
- bool operator==(const xor_combine<UniformRandomNumberGenerator1, s1,
- UniformRandomNumberGenerator2, s2> & x,
- (const xor_combine<UniformRandomNumberGenerator1, s1,
- UniformRandomNumberGenerator2, s2> & y);
- template<class UniformRandomNumberGenerator1, int s1,
- class UniformRandomNumberGenerator2, int s2>
- bool operator!=(const xor_combine<UniformRandomNumberGenerator1, s1,
- UniformRandomNumberGenerator2, s2> & x,
- (const xor_combine<UniformRandomNumberGenerator1, s1,
- UniformRandomNumberGenerator2, s2> & y);
-
- template<class CharT, class traits,
- class UniformRandomNumberGenerator1, int s1,
- class UniformRandomNumberGenerator2, int s2>
- basic_ostream<CharT, traits>& operator<<(basic_ostream<CharT, traits>& os,
- const xor_combine<UniformRandomNumberGenerator1, s1,
- UniformRandomNumberGenerator2, s2> & x);
- template<class CharT, class traits,
- class UniformRandomNumberGenerator1, int s1,
- class UniformRandomNumberGenerator2, int s2>
- basic_istream<CharT, traits>& operator>>(basic_istream<CharT, traits>& is,
- xor_combine<UniformRandomNumberGenerator1, s1,
- UniformRandomNumberGenerator2, s2> & x);
-
-}
-</pre>The template parameters <code>UniformRandomNumberGenerator1</code> and
-<code>UniformRandomNumberGenerator1</code> shall denote classes that satisfy
-all the requirements of a uniform random number generator, given in tables in
-section x.x . The size of the state is the size of <code><em>b1</em></code>
-plus the size of <code><em>b2</em></code>.
- <pre>
- xor_combine()
-</pre><strong>Effects:</strong> Constructs a <code>xor_combine</code> engine.
-To construct each of the subobjects <em>b1</em> and <em>b2</em>, invokes
-their respective default constructors.
- <pre>
- xor_combine(const base1_type & rng1, const base2_type & rng2)
-</pre><strong>Effects:</strong> Constructs a <code>xor_combine</code> engine.
-Initializes <em>b1</em> with a copy of <code>rng1</code> and <em>b2</em> with
-a copy of <code>rng2</code>.
- <pre>
- template<class In> xor_combine(In& first, In last)
-</pre><strong>Effects:</strong> Constructs a <code>xor_combine</code> engine.
-To construct the subobject <em>b1</em>, invokes the <code>b1(first,
-last)</code> constructor. Then, to construct the subobject <em>b2</em>,
-invokes the <code>b2(first, last)</code> constructor.
- <pre>
- void seed()
-</pre><strong>Effects:</strong> Invokes <code><em>b1</em>.seed()</code> and
-<code><em>b2</em>.seed()</code>.
- <pre>
- template<class In> void seed(In& first, In last)
-</pre><strong>Effects:</strong> Invokes <code><em>b1</em>.seed(first,
-last)</code>, then invokes <code><em>b2</em>.seed(first, last)</code>.
- <pre>
- const base1_type& base1() const
-</pre><strong>Returns:</strong> <em>b1</em>
- <pre>
- const base2_type& base2() const
-</pre><strong>Returns:</strong> <em>b2</em>
- <pre>
- result_type operator()()
-</pre><strong>Returns:</strong> (<code><em>b1</em>() << s1) ^
-(<em>b2</em>() << s2)</code>.
- <pre>
- template<class CharT, class traits,
- class UniformRandomNumberGenerator1, int s1,
- class UniformRandomNumberGenerator2, int s2>
- basic_ostream<CharT, traits>& operator<<(basic_ostream<CharT, traits>& os,
- const xor_combine<UniformRandomNumberGenerator1, s1,
- UniformRandomNumberGenerator2, s2> & x);
-</pre><strong>Effects:</strong> Writes <code><em>b1</em></code>, then <code>
- <em>b2</em></code> to <code>os</code>.
-
- <h3>Engines with predefined parameters</h3>
- <pre>
-namespace std {
- typedef linear_congruential</* <em>implementation defined</em> */, 16807, 0, 2147483647> minstd_rand0;
- typedef linear_congruential</* <em>implementation defined</em> */, 48271, 0, 2147483647> minstd_rand;
-
- typedef mersenne_twister</* <em>implementation defined</em> */,32,624,397,31,0x9908b0df,11,7,0x9d2c5680,15,0xefc60000,18> mt19937;
-
- typedef subtract_with_carry_01<float, 24, 10, 24> ranlux_base_01;
- typedef subtract_with_carry_01<double, 48, 10, 24> ranlux64_base_01;
-
- typedef discard_block<subtract_with_carry</* <em>implementation defined</em> */, (1<<24), 10, 24>, 223, 24> ranlux3;
- typedef discard_block<subtract_with_carry</* <em>implementation defined</em> */, (1<<24), 10, 24>, 389, 24> ranlux4;
-
- typedef discard_block<subtract_with_carry_01<float, 24, 10, 24>, 223, 24> ranlux3_01;
- typedef discard_block<subtract_with_carry_01<float, 24, 10, 24>, 389, 24> ranlux4_01;
-}
-</pre>For a default-constructed <code>minstd_rand0</code> object, x(10000) =
-1043618065. For a default-constructed <code>minstd_rand</code> object,
-x(10000) = 399268537.
-
- <p>For a default-constructed <code>mt19937</code> object, x(10000) =
- 3346425566.</p>
-
- <p>For a default-constructed <code>ranlux3</code> object, x(10000) =
- 5957620. For a default-constructed <code>ranlux4</code> object, x(10000) =
- 8587295. For a default-constructed <code>ranlux3_01</code> object, x(10000)
- = 5957620 * 2<sup>-24</sup>. For a default-constructed
- <code>ranlux4_01</code> object, x(10000) = 8587295 * 2<sup>-24</sup>.</p>
-
- <h3>Class <code>random_device</code></h3>A <code>random_device</code>
- produces non-deterministic random numbers. It satisfies all the
- requirements of a uniform random number generator (given in tables in
- section x.x). Descriptions are provided here only for operations on the
- engines that are not described in one of these tables or for operations
- where there is additional semantic information.
-
- <p>If implementation limitations prevent generating non-deterministic
- random numbers, the implementation can employ a pseudo-random number
- engine.</p>
- <pre>
-namespace std {
- class random_device
- {
- public:
- // <em>types</em>
- typedef unsigned int result_type;
-
- // <em>constructors, destructors and member functions</em>
- explicit random_device(const std::string& token = /* <em>implementation-defined</em> */);
- result_type min() const;
- result_type max() const;
- double entropy() const;
- result_type operator()();
-
- private:
- random_device(const random_device& );
- void operator=(const random_device& );
- };
-}
-</pre>
- <pre>
- explicit random_device(const std::string& token = /* <em>implementation-defined</em> */)
-</pre><strong>Effects:</strong> Constructs a <code>random_device</code>
-non-deterministic random number engine. The semantics and default value of
-the <code>token</code> parameter are implementation-defined. [Footnote: The
-parameter is intended to allow an implementation to differentiate between
-different sources of randomness.]<br>
- <strong>Throws:</strong> A value of some type derived from
- <code>exception</code> if the <code>random_device</code> could not be
- initialized.
- <pre>
- result_type min() const
-</pre><strong>Returns:</strong>
-<code>numeric_limits<result_type>::min()</code>
- <pre>
- result_type max() const
-</pre><strong>Returns:</strong>
-<code>numeric_limits<result_type>::max()</code>
- <pre>
- double entropy() const
-</pre><strong>Returns:</strong> An entropy estimate for the random numbers
-returned by operator(), in the range <code>min()</code> to log<sub>2</sub>(
-<code>max()</code>+1). A deterministic random number generator (e.g. a
-pseudo-random number engine) has entropy 0.<br>
- <strong>Throws:</strong> Nothing.
- <pre>
- result_type operator()()
-</pre><strong>Returns:</strong> A non-deterministic random value, uniformly
-distributed between <code>min()</code> and <code>max()</code>, inclusive. It
-is implementation-defined how these values are generated.<br>
- <strong>Throws:</strong> A value of some type derived from
- <code>exception</code> if a random number could not be obtained.
-
- <h3>Random distribution class templates</h3>The class templates specified
- in this section satisfy all the requirements of a random distribution
- (given in tables in section x.x). Descriptions are provided here only for
- operations on the distributions that are not described in one of these
- tables or for operations where there is additional semantic information.
-
- <p>A template parameter named <code>IntType</code> shall denote a type that
- represents an integer number. This type shall meet the requirements for a
- numeric type (26.1 [lib.numeric.requirements]), the binary operators +, -,
- *, /, % shall be applicable to it, and a conversion from <code>int</code>
- shall exist. <em>[Footnote: The built-in types <code>int</code> and
- <code>long</code> meet these requirements.]</em></p>
-
- <p>Given an object whose type is specified in this subclause, if the
- lifetime of the uniform random number generator referred to in the
- constructor invocation for that object has ended, any use of that object is
- undefined.</p>
-
- <p>No function described in this section throws an exception, unless an
- operation on values of <code>IntType</code> or <code>RealType</code> throws
- an exception. <em>[Note: Then, the effects are undefined, see
- [lib.numeric.requirements]. ]</em></p>
-
- <p>The algorithms for producing each of the specified distributions are
- implementation-defined.</p>
-
- <h4>Class template <code>uniform_int</code></h4>A <code>uniform_int</code>
- random distribution produces integer random numbers x in the range min
- <= x <= max, with equal probability. min and max are the parameters
- of the distribution.
-
- <p>A <code>uniform_int</code> random distribution satisfies all the
- requirements of a uniform random number generator (given in tables in
- section x.x).</p>
- <pre>
-namespace std {
- template<class IntType = int>
- class uniform_int
- {
- public:
- // <em>types</em>
- typedef IntType input_type;
- typedef IntType result_type;
-
- // <em> constructors and member function</em>
- explicit uniform_int(IntType min = 0, IntType max = 9);
- result_type min() const;
- result_type max() const;
- void reset();
- template<class UniformRandomNumberGenerator>
- result_type operator()(UniformRandomNumberGenerator& urng);
- template<class UniformRandomNumberGenerator>
- result_type operator()(UniformRandomNumberGenerator& urng, result_type n);
- };
-}
-</pre>
- <pre>
- uniform_int(IntType min = 0, IntType max = 9)
-</pre><strong>Requires:</strong> min <= max<br>
- <strong>Effects:</strong> Constructs a <code>uniform_int</code> object.
- <code>min</code> and <code>max</code> are the parameters of the
- distribution.
- <pre>
- result_type min() const
-</pre><strong>Returns:</strong> The "min" parameter of the distribution.
- <pre>
- result_type max() const
-</pre><strong>Returns:</strong> The "max" parameter of the distribution.
- <pre>
- result_type operator()(UniformRandomNumberGenerator& urng, result_type n)
-</pre><strong>Returns:</strong> A uniform random number x in the range 0
-<= x < n. <em>[Note: This allows a <code>variate_generator</code>
-object with a <code>uniform_int</code> distribution to be used with
-std::random_shuffe, see [lib.alg.random.shuffle]. ]</em>
-
- <h4>Class template <code>bernoulli_distribution</code></h4>A
- <code>bernoulli_distribution</code> random distribution produces
- <code>bool</code> values distributed with probabilities p(true) = p and
- p(false) = 1-p. p is the parameter of the distribution.
- <pre>
-namespace std {
- template<class RealType = double>
- class bernoulli_distribution
- {
- public:
- // <em>types</em>
- typedef int input_type;
- typedef bool result_type;
-
- // <em> constructors and member function</em>
- explicit bernoulli_distribution(const RealType& p = RealType(0.5));
- RealType p() const;
- void reset();
- template<class UniformRandomNumberGenerator>
- result_type operator()(UniformRandomNumberGenerator& urng);
- };
-}
-</pre>
- <pre>
- bernoulli_distribution(const RealType& p = RealType(0.5))
-</pre><strong>Requires:</strong> 0 <= p <= 1<br>
- <strong>Effects:</strong> Constructs a <code>bernoulli_distribution</code>
- object. <code>p</code> is the parameter of the distribution.
- <pre>
- RealType p() const
-</pre><strong>Returns:</strong> The "p" parameter of the distribution.
-
- <h4>Class template <code>geometric_distribution</code></h4>A
- <code>geometric_distribution</code> random distribution produces integer
- values <em>i</em> >= 1 with p(i) = (1-p) * p<sup>i-1</sup>. p is the
- parameter of the distribution.
- <pre>
-namespace std {
- template<class IntType = int, class RealType = double>
- class geometric_distribution
- {
- public:
- // <em>types</em>
- typedef RealType input_type;
- typedef IntType result_type;
-
- // <em> constructors and member function</em>
- explicit geometric_distribution(const RealType& p = RealType(0.5));
- RealType p() const;
- void reset();
- template<class UniformRandomNumberGenerator>
- result_type operator()(UniformRandomNumberGenerator& urng);
- };
-}
-</pre>
- <pre>
- geometric_distribution(const RealType& p = RealType(0.5))
-</pre><strong>Requires:</strong> 0 < p < 1<br>
- <strong>Effects:</strong> Constructs a <code>geometric_distribution</code>
- object; <code>p</code> is the parameter of the distribution.
- <pre>
- RealType p() const
-</pre><strong>Returns:</strong> The "p" parameter of the distribution.
-
- <h4>Class template <code>poisson_distribution</code></h4>A
- <code>poisson_distribution</code> random distribution produces integer
- values <em>i</em> >= 0 with p(i) = exp(-mean) * mean<sup>i</sup> / i!.
- mean is the parameter of the distribution.
- <pre>
-namespace std {
- template<class IntType = int, class RealType = double>
- class poisson_distribution
- {
- public:
- // <em>types</em>
- typedef RealType input_type;
- typedef IntType result_type;
-
- // <em> constructors and member function</em>
- explicit poisson_distribution(const RealType& mean = RealType(1));
- RealType mean() const;
- void reset();
- template<class UniformRandomNumberGenerator>
- result_type operator()(UniformRandomNumberGenerator& urng);
- };
-}
-</pre>
- <pre>
- poisson_distribution(const RealType& mean = RealType(1))
-</pre><strong>Requires:</strong> mean > 0<br>
- <strong>Effects:</strong> Constructs a <code>poisson_distribution</code>
- object; <code>mean</code> is the parameter of the distribution.
- <pre>
- RealType mean() const
-</pre><strong>Returns:</strong> The "mean" parameter of the distribution.
-
- <h4>Class template <code>binomial_distribution</code></h4>A
- <code>binomial_distribution</code> random distribution produces integer
- values <em>i</em> >= 0 with p(i) = (n over i) * p<sup>i</sup> *
- (1-p)<sup>t-i</sup>. t and p are the parameters of the distribution.
- <pre>
-namespace std {
- template<class IntType = int, class RealType = double>
- class binomial_distribution
- {
- public:
- // <em>types</em>
- typedef /* <em>implementation-defined</em> */ input_type;
- typedef IntType result_type;
-
- // <em> constructors and member function</em>
- explicit binomial_distribution(IntType t = 1, const RealType& p = RealType(0.5));
- IntType t() const;
- RealType p() const;
- void reset();
- template<class UniformRandomNumberGenerator>
- result_type operator()(UniformRandomNumberGenerator& urng);
- };
-}
-</pre>
- <pre>
- binomial_distribution(IntType t = 1, const RealType& p = RealType(0.5))
-</pre><strong>Requires:</strong> 0 <= p <= 1 and t >= 0<br>
- <strong>Effects:</strong> Constructs a <code>binomial_distribution</code>
- object; <code>t</code> and <code>p</code> are the parameters of the
- distribution.
- <pre>
- IntType t() const
-</pre><strong>Returns:</strong> The "t" parameter of the distribution.
- <pre>
- RealType p() const
-</pre><strong>Returns:</strong> The "p" parameter of the distribution.
-
- <h4>Class template <code>uniform_real</code></h4>A
- <code>uniform_real</code> random distribution produces floating-point
- random numbers x in the range min <= x <= max, with equal
- probability. min and max are the parameters of the distribution.
-
- <p>A <code>uniform_real</code> random distribution satisfies all the
- requirements of a uniform random number generator (given in tables in
- section x.x).</p>
- <pre>
-namespace std {
- template<class RealType = double>
- class uniform_real
- {
- public:
- // <em>types</em>
- typedef RealType input_type;
- typedef RealType result_type;
-
- // <em> constructors and member function</em>
- explicit uniform_real(RealType min = RealType(0), RealType max = RealType(1));
- result_type min() const;
- result_type max() const;
- void reset();
- template<class UniformRandomNumberGenerator>
- result_type operator()(UniformRandomNumberGenerator& urng);
- };
-}
-</pre>
- <pre>
- uniform_real(RealType min = RealType(0), RealType max = RealType(1))
-</pre><strong>Requires:</strong> min <= max<br>
- <strong>Effects:</strong> Constructs a <code>uniform_real</code> object;
- <code>min</code> and <code>max</code> are the parameters of the
- distribution.
- <pre>
- result_type min() const
-</pre><strong>Returns:</strong> The "min" parameter of the distribution.
- <pre>
- result_type max() const
-</pre><strong>Returns:</strong> The "max" parameter of the distribution.
-
- <h4>Class template <code>exponential_distribution</code></h4>An
- <code>exponential_distribution</code> random distribution produces random
- numbers x > 0 distributed with probability density function p(x) =
- lambda * exp(-lambda * x), where lambda is the parameter of the
- distribution.
- <pre>
-namespace std {
- template<class RealType = double>
- class exponential_distribution
- {
- public:
- // <em>types</em>
- typedef RealType input_type;
- typedef RealType result_type;
-
- // <em> constructors and member function</em>
- explicit exponential_distribution(const result_type& lambda = result_type(1));
- RealType lambda() const;
- void reset();
- template<class UniformRandomNumberGenerator>
- result_type operator()(UniformRandomNumberGenerator& urng);
- };
-}
-</pre>
- <pre>
- exponential_distribution(const result_type& lambda = result_type(1))
-</pre><strong>Requires:</strong> lambda > 0<br>
- <strong>Effects:</strong> Constructs an
- <code>exponential_distribution</code> object with <code>rng</code> as the
- reference to the underlying source of random numbers. <code>lambda</code>
- is the parameter for the distribution.
- <pre>
- RealType lambda() const
-</pre><strong>Returns:</strong> The "lambda" parameter of the distribution.
-
- <h4>Class template <code>normal_distribution</code></h4>A
- <code>normal_distribution</code> random distribution produces random
- numbers x distributed with probability density function p(x) =
- 1/sqrt(2*pi*sigma) * exp(- (x-mean)<sup>2</sup> / (2*sigma<sup>2</sup>) ),
- where mean and sigma are the parameters of the distribution.
- <pre>
-namespace std {
- template<class RealType = double>
- class normal_distribution
- {
- public:
- // <em>types</em>
- typedef RealType input_type;
- typedef RealType result_type;
-
- // <em> constructors and member function</em>
- explicit normal_distribution(base_type & rng, const result_type& mean = 0,
- const result_type& sigma = 1);
- RealType mean() const;
- RealType sigma() const;
- void reset();
- template<class UniformRandomNumberGenerator>
- result_type operator()(UniformRandomNumberGenerator& urng);
- };
-}
-</pre>
- <pre>
- explicit normal_distribution( const result_type& mean = 0,
- const result_type& sigma = 1);
-</pre><strong>Requires:</strong> sigma > 0<br>
- <strong>Effects:</strong> Constructs a <code>normal_distribution</code>
- object; <code>mean</code> and <code>sigma</code> are the parameters for the
- distribution.
- <pre>
- RealType mean() const
-</pre><strong>Returns:</strong> The "mean" parameter of the distribution.
- <pre>
- RealType sigma() const
-</pre><strong>Returns:</strong> The "sigma" parameter of the distribution.
-
- <h4>Class template <code>gamma_distribution</code></h4>A
- <code>gamma_distribution</code> random distribution produces random numbers
- x distributed with probability density function p(x) = 1/Gamma(alpha) *
- x<sup>alpha-1</sup> * exp(-x), where alpha is the parameter of the
- distribution.
- <pre>
-namespace std {
- template<class RealType = double>
- class gamma_distribution
- {
- public:
- // <em>types</em>
- typedef RealType input_type;
- typedef RealType result_type;
-
- // <em> constructors and member function</em>
- explicit gamma_distribution(const result_type& alpha = result_type(1));
- RealType alpha() const;
- void reset();
- template<class UniformRandomNumberGenerator>
- result_type operator()(UniformRandomNumberGenerator& urng);
- };
-}
-</pre>
- <pre>
- explicit gamma_distribution(const result_type& alpha = result_type(1));
-</pre><strong>Requires:</strong> alpha > 0<br>
- <strong>Effects:</strong> Constructs a <code>gamma_distribution</code>
- object; <code>alpha</code> is the parameter for the distribution.
- <pre>
- RealType alpha() const
-</pre><strong>Returns:</strong> The "alpha" parameter of the distribution.
-
- <h2>V. Acknowledgements</h2>
-
- <ul>
- <li>Thanks to Walter Brown, Mark Fischler and Marc Paterno from Fermilab
- for input about the requirements of high-energy physics.</li>
-
- <li>Thanks to David Abrahams for additional comments on the design.</li>
-
- <li>Thanks to the Boost community for a platform for
- experimentation.</li>
- </ul>
-
- <h2>VI. References</h2>
-
- <ul>
- <li>William H. Press, Saul A. Teukolsky, William A. Vetterling, Brian P.
- Flannery, "Numerical Recipes in C: The art of scientific computing", 2nd
- ed., 1992, pp. 274-328</li>
-
- <li>Bruce Schneier, "Applied Cryptography", 2nd ed., 1996, ch. 16-17. [I
- haven't read this myself. Yet.]</li>
-
- <li>D. H. Lehmer, "Mathematical methods in large-scale computing units",
- Proc. 2nd Symposium on Large-Scale Digital Calculating Machines, Harvard
- University Press, 1951, pp. 141-146</li>
-
- <li>P.A. Lewis, A.S. Goodman, J.M. Miller, "A pseudo-random number
- generator for the System/360", IBM Systems Journal, Vol. 8, No. 2, 1969,
- pp. 136-146</li>
-
- <li>Stephen K. Park and Keith W. Miller, "Random Number Generators: Good
- ones are hard to find", Communications of the ACM, Vol. 31, No. 10,
- October 1988, pp. 1192-1201</li>
-
- <li>Makoto Matsumoto and Takuji Nishimura, "Mersenne Twister: A
- 623-dimensionally equidistributed uniform pseudo-random number
- generator", ACM Transactions on Modeling and Computer Simulation: Special
- Issue on Uniform Random Number Generation, Vol. 8, No. 1, January 1998,
- pp. 3-30. http://www.math.keio.ac.jp/matumoto/emt.html.>
-
- <li>Donald E. Knuth, "The Art of Computer Programming, Vol. 2", 3rd ed.,
- 1997, pp. 1-193.</li>
-
- <li>Carter Bays and S.D. Durham, "Improving a poor random number
- generator", ACM Transactions on Mathematical Software, Vol. 2, 1979, pp.
- 59-64.</li>
-
- <li>Martin Lüscher, "A portable high-quality random number generator
- for lattice field theory simulations.", Computer Physics Communications,
- Vol. 79, 1994, pp. 100-110.</li>
-
- <li>William J. Hurd, "Efficient Generation of Statistically Good
- Pseudonoise by Linearly Interconnected Shift Registers", Technical Report
- 32-1526, Volume XI, The Deep Space Network Progress Report for July and
- August 1972, NASA Jet Propulsion Laboratory, 1972 and IEEE Transactions
- on Computers Vol. 23, 1974.</li>
-
- <li>Pierre L'Ecuyer, "Efficient and Portable Combined Random Number
- Generators", Communications of the ACM, Vol. 31, pp. 742-749+774,
- 1988.</li>
-
- <li>Pierre L'Ecuyer, "Maximally equidistributed combined Tausworthe
- generators", Mathematics of Computation Vol. 65, pp. 203-213, 1996.</li>
-
- <li>Pierre L'Ecuyer, "Good parameters and implementations for combined
- multple recursive random number generators", Operations Research Vol. 47,
- pp. 159-164, 1999.</li>
-
- <li>S. Kirkpatrick and E. Stoll, "A very fast shift-register sequence
- random number generator", Journal of Computational Physics, Vol. 40, pp.
- 517-526, 1981.</li>
-
- <li>R. C. Tausworthe, "Random numbers generated by iinear recurrence
- modulo two", Mathematics of Computation, Vol. 19, pp. 201-209, 1965.</li>
-
- <li>George Marsaglia and Arif Zaman, "A New Class of Random Number
- Generators", Annals of Applied Probability, Vol. 1, No. 3, 1991.</li>
- </ul>
- <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
- 05 December, 2006</p>
-
- <p><i>Copyright © 2002 <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 LICENSE_1_0.txt or
- copy at <a href=
- "http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt>)</i></p>
-</body>
-</html>

Next message: erwann.rogard_at_[hidden]: "[Boost-commit] svn:boost r60173 - in sandbox/statistics/detail/assign: boost/assign/auto_size/array libs/assign/example"
Previous message: erwann.rogard_at_[hidden]: "[Boost-commit] svn:boost r60171 - sandbox/statistics/detail/assign/libs/assign/doc"

Date view	Thread view	Subject view	Author view

Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk