|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r59910 - in trunk: boost boost/random libs/random libs/random/doc libs/random/example
From: steven_at_[hidden]
Date: 2010-02-25 13:13:42
Author: steven_watanabe
Date: 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
New Revision: 59910
URL: http://svn.boost.org/trac/boost/changeset/59910
Log:
Add Quickbook/Doxygen documentation
Added:
trunk/libs/random/doc/
trunk/libs/random/doc/Jamfile.v2 (contents, props changed)
trunk/libs/random/doc/concepts.qbk (contents, props changed)
trunk/libs/random/doc/distribution_performance_linux.qbk (contents, props changed)
trunk/libs/random/doc/distribution_performance_windows.qbk (contents, props changed)
trunk/libs/random/doc/distributions.qbk (contents, props changed)
trunk/libs/random/doc/generator_defs.qbk (contents, props changed)
trunk/libs/random/doc/generator_performance_linux.qbk (contents, props changed)
trunk/libs/random/doc/generator_performance_windows.qbk (contents, props changed)
trunk/libs/random/doc/generators.qbk (contents, props changed)
trunk/libs/random/doc/nondet_random.qbk (contents, props changed)
trunk/libs/random/doc/performance.qbk (contents, props changed)
trunk/libs/random/doc/performance_data.qbk (contents, props changed)
trunk/libs/random/doc/random.qbk (contents, props changed)
trunk/libs/random/doc/random_number_generator.qbk (contents, props changed)
trunk/libs/random/doc/tutorial.qbk (contents, props changed)
trunk/libs/random/example/
trunk/libs/random/example/Jamfile.v2 (contents, props changed)
trunk/libs/random/example/die.cpp (contents, props changed)
trunk/libs/random/example/weighted_die.cpp (contents, props changed)
trunk/libs/random/generate_table.cpp (contents, props changed)
Text files modified:
trunk/boost/nondet_random.hpp | 73 ++++++++++++++++++++
trunk/boost/random.hpp | 9 ++
trunk/boost/random/additive_combine.hpp | 106 +++++++++++++++++++++++++++++
trunk/boost/random/bernoulli_distribution.hpp | 30 ++++++++
trunk/boost/random/binomial_distribution.hpp | 39 +++++++++-
trunk/boost/random/cauchy_distribution.hpp | 33 +++++++++
trunk/boost/random/discard_block.hpp | 9 ++
trunk/boost/random/exponential_distribution.hpp | 6 +
trunk/boost/random/gamma_distribution.hpp | 11 ++
trunk/boost/random/geometric_distribution.hpp | 26 ++++++
trunk/boost/random/inversive_congruential.hpp | 44 ++++++++++++
trunk/boost/random/lagged_fibonacci.hpp | 142 +++++++++++++++++++++++++++++++++++++++
trunk/boost/random/linear_congruential.hpp | 123 ++++++++++++++++++++++++++++++++++
trunk/boost/random/linear_feedback_shift.hpp | 11 ++
trunk/boost/random/lognormal_distribution.hpp | 14 +++
trunk/boost/random/mersenne_twister.hpp | 86 ++++++++++++++++++++++-
trunk/boost/random/normal_distribution.hpp | 19 +++++
trunk/boost/random/poisson_distribution.hpp | 16 ++++
trunk/boost/random/random_number_generator.hpp | 17 ++++
trunk/boost/random/ranlux.hpp | 31 ++++++++
trunk/boost/random/shuffle_output.hpp | 61 ++++++++++++++++
trunk/boost/random/subtract_with_carry.hpp | 25 +++++-
trunk/boost/random/triangle_distribution.hpp | 20 +++++
trunk/boost/random/uniform_01.hpp | 49 +++++++++++++
trunk/boost/random/uniform_int.hpp | 27 +++++++
trunk/boost/random/uniform_on_sphere.hpp | 14 +++
trunk/boost/random/uniform_real.hpp | 24 ++++++
trunk/boost/random/uniform_smallint.hpp | 50 ++++++++++++++
trunk/boost/random/variate_generator.hpp | 83 +++++++++++++++++++++++
trunk/boost/random/xor_combine.hpp | 52 ++++++++++++++
trunk/libs/random/random_speed.cpp | 77 ++++++++++++++++++--
31 files changed, 1278 insertions(+), 49 deletions(-)
Modified: trunk/boost/nondet_random.hpp
==============================================================================
--- trunk/boost/nondet_random.hpp (original)
+++ trunk/boost/nondet_random.hpp 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -26,7 +26,56 @@
namespace boost {
-// use some OS service to generate non-deterministic random numbers
+/**
+ * Class \random_device models a \nondeterministic_random_number_generator.
+ * 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 random_device must not be implemented. See
+ *
+ * @blockquote
+ * "Randomness Recommendations for Security", D. Eastlake, S. Crocker,
+ * J. Schiller, Network Working Group, RFC 1750, December 1994
+ * @endblockquote
+ *
+ * for further discussions.
+ *
+ * @xmlnote
+ * 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.
+ * @endxmlnote
+ *
+ * <b>Implementation Note for Linux</b>
+ *
+ * On the Linux operating system, token 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, @c std::ios_base::failure is thrown. By default,
+ * \random_device uses the /dev/urandom pseudo-device to retrieve
+ * the random numbers. Another option would be to specify the /dev/random
+ * pseudo-device, which blocks on reads if the entropy pool has no more
+ * random bits available.
+ *
+ * <b>Performance</b>
+ *
+ * The test program <a href="\boost/libs/random/nondet_random_speed.cpp">
+ * nondet_random_speed.cpp</a> measures the execution times of the
+ * nondet_random.hpp 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.
+ *
+ * <table cols="2">
+ * <tr><th>class</th><th>time per invocation [usec]</th></tr>
+ * <tr><td> @xmlonly <classname alt="boost::random_device">random_device</classname> @endxmlonly </td><td>92.0</td></tr>
+ * </table>
+ *
+ * The measurement error is estimated at +/- 1 usec.
+ */
class random_device : private noncopyable
{
public:
@@ -35,11 +84,33 @@
BOOST_STATIC_CONSTANT(result_type, min_value = integer_traits<result_type>::const_min);
BOOST_STATIC_CONSTANT(result_type, max_value = integer_traits<result_type>::const_max);
+ /**
+ * Returns: The smallest value that the \random_device can produce.
+ */
result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return min_value; }
+ /**
+ * Returns: The largest value that the \random_device can produce.
+ */
result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return max_value; }
+ /**
+ * Constructs a @c random_device, optionally using the given token as an
+ * access specification (for example, a URL) to some implementation-defined
+ * service for monitoring a stochastic process.
+ */
explicit random_device(const std::string& token = default_token);
~random_device();
+ /**
+ * Returns: An entropy estimate for the random numbers returned by
+ * operator(), in the range min() to log2( max()+1). A deterministic
+ * random number generator (e.g. a pseudo-random number engine)
+ * has entropy 0.
+ *
+ * Throws: Nothing.
+ */
double entropy() const;
+ /**
+ * Returns: A random value in the range [min, max]
+ */
unsigned int operator()();
private:
Modified: trunk/boost/random.hpp
==============================================================================
--- trunk/boost/random.hpp (original)
+++ trunk/boost/random.hpp 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -47,6 +47,15 @@
#include <boost/random/variate_generator.hpp>
namespace boost {
+ /**
+ * The specialization taus88 was suggested in
+ *
+ * @blockquote
+ * "Maximally Equidistributed Combined Tausworthe Generators",
+ * Pierre L'Ecuyer, Mathematics of Computation, Volume 65,
+ * Number 213, January 1996, Pages 203-213
+ * @endblockquote
+ */
typedef random::xor_combine<random::xor_combine<random::linear_feedback_shift<uint32_t, 32, 31, 13, 12, 0>, 0,
random::linear_feedback_shift<uint32_t, 32, 29, 2, 4, 0>, 0, 0>, 0,
random::linear_feedback_shift<uint32_t, 32, 28, 3, 17, 0>, 0, 0> taus88;
Modified: trunk/boost/random/additive_combine.hpp
==============================================================================
--- trunk/boost/random/additive_combine.hpp (original)
+++ trunk/boost/random/additive_combine.hpp 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -26,7 +26,24 @@
namespace boost {
namespace random {
-// L'Ecuyer 1988
+/**
+ * An instantiation of class template \additive_combine model a
+ * \pseudo_random_number_generator. It combines two multiplicative
+ * \linear_congruential number generators, i.e. those with @c c = 0.
+ * It is described in
+ *
+ * @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
+ * @endblockquote
+ *
+ * The template parameters MLCG1 and MLCG2 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 MLCG1.
+ *
+ * The template parameter @c val is the validation value checked by validation.
+ */
template<class MLCG1, class MLCG2,
#ifndef BOOST_NO_DEPENDENT_TYPES_IN_TEMPLATE_VALUE_PARAMETERS
typename MLCG1::result_type
@@ -47,30 +64,71 @@
#else
enum { has_fixed_range = false };
#endif
+ /**
+ * Returns: The smallest value that the generator can produce
+ */
result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return 1; }
+ /**
+ * Returns: The largest value that the generator can produce
+ */
result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return (_mlcg1.max)()-1; }
+ /**
+ * Constructs an \additive_combine generator using the
+ * default constructors of the two base generators.
+ */
additive_combine() : _mlcg1(), _mlcg2() { }
+ /**
+ * Constructs an \additive_combine generator, using aseed as
+ * the constructor argument for both base generators.
+ */
+ explicit additive_combine(result_type aseed)
+ : _mlcg1(aseed), _mlcg2(aseed) { }
+ /**
+ * Constructs an \additive_combine generator, using
+ * @c seed1 and @c seed2 as the constructor argument to
+ * the first and second base generators, respectively.
+ */
additive_combine(typename MLCG1::result_type seed1,
typename MLCG2::result_type seed2)
: _mlcg1(seed1), _mlcg2(seed2) { }
- additive_combine(result_type aseed)
- : _mlcg1(aseed), _mlcg2(aseed) { }
+ /**
+ * Contructs an \additive_combine generator with
+ * values from the range defined by the input iterators first
+ * and last. first will be modified to point to the element
+ * after the last one used.
+ *
+ * Throws: @c std::invalid_argument if the input range is too small.
+ *
+ * Exception Safety: Basic
+ */
template<class It> additive_combine(It& first, It last)
: _mlcg1(first, last), _mlcg2(first, last) { }
+ /**
+ * Seeds an \additive_combine generator using the default
+ * seeds of the two base generators.
+ */
void seed()
{
_mlcg1.seed();
_mlcg2.seed();
}
+ /**
+ * Seeds an \additive_combine generator, using @c aseed as the
+ * seed for both base generators.
+ */
void seed(result_type aseed)
{
_mlcg1.seed(aseed);
_mlcg2.seed(aseed);
}
+ /**
+ * Seeds an \additive_combine generator, using @c seed1 and @c seed2 as
+ * the seeds to the first and second base generators, respectively.
+ */
void seed(typename MLCG1::result_type seed1,
typename MLCG2::result_type seed2)
{
@@ -78,36 +136,69 @@
_mlcg2.seed(seed2);
}
+ /**
+ * Seeds an \additive_combine generator with
+ * values from the range defined by the input iterators first
+ * and last. first will be modified to point to the element
+ * after the last one used.
+ *
+ * Throws: @c std::invalid_argument if the input range is too small.
+ *
+ * Exception Safety: Basic
+ */
template<class It> void seed(It& first, It last)
{
_mlcg1.seed(first, last);
_mlcg2.seed(first, last);
}
+ /**
+ * Returns: the next value of the generator
+ */
result_type operator()() {
result_type z = _mlcg1() - _mlcg2();
if(z < 1)
z += MLCG1::modulus-1;
return z;
}
+
static bool validation(result_type x) { return val == x; }
#ifndef BOOST_NO_OPERATORS_IN_NAMESPACE
#ifndef BOOST_RANDOM_NO_STREAM_OPERATORS
+ /**
+ * Writes the state of an \additive_combine generator to a @c
+ * std::ostream. The textual representation of an \additive_combine
+ * generator is the textual representation of the first base
+ * generator followed by the textual representation of the
+ * second base generator.
+ */
template<class CharT, class Traits>
friend std::basic_ostream<CharT,Traits>&
operator<<(std::basic_ostream<CharT,Traits>& os, const additive_combine& r)
{ os << r._mlcg1 << " " << r._mlcg2; return os; }
+ /**
+ * Reads the state of an \additive_combine generator from a
+ * @c std::istream.
+ */
template<class CharT, class Traits>
friend std::basic_istream<CharT,Traits>&
operator>>(std::basic_istream<CharT,Traits>& is, additive_combine& r)
{ is >> r._mlcg1 >> std::ws >> r._mlcg2; return is; }
#endif
+ /**
+ * Returns: true iff the two \additive_combine generators will
+ * produce the same sequence of values.
+ */
friend bool operator==(const additive_combine& x, const additive_combine& y)
{ return x._mlcg1 == y._mlcg1 && x._mlcg2 == y._mlcg2; }
+ /**
+ * Returns: true iff the two \additive_combine generators will
+ * produce different sequences of values.
+ */
friend bool operator!=(const additive_combine& x, const additive_combine& y)
{ return !(x == y); }
#else
@@ -117,6 +208,7 @@
bool operator!=(const additive_combine& rhs) const
{ return !(*this == rhs); }
#endif
+
private:
MLCG1 _mlcg1;
MLCG2 _mlcg2;
@@ -124,6 +216,14 @@
} // namespace random
+/**
+ * The specialization \ecuyer1988 was suggested in
+ *
+ * @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
+ * @endblockquote
+ */
typedef random::additive_combine<
random::linear_congruential<int32_t, 40014, 0, 2147483563, 0>,
random::linear_congruential<int32_t, 40692, 0, 2147483399, 0>,
Modified: trunk/boost/random/bernoulli_distribution.hpp
==============================================================================
--- trunk/boost/random/bernoulli_distribution.hpp (original)
+++ trunk/boost/random/bernoulli_distribution.hpp 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -22,7 +22,12 @@
namespace boost {
-// Bernoulli distribution: p(true) = p, p(false) = 1-p (boolean)
+/**
+ * Instantiations of class template \bernoulli_distribution model a
+ * \random_distribution. Such a random distribution produces bool values
+ * distributed with probabilities P(true) = p and P(false) = 1-p. p is
+ * the parameter of the distribution.
+ */
template<class RealType = double>
class bernoulli_distribution
{
@@ -33,6 +38,12 @@
typedef int input_type;
typedef bool result_type;
+ /**
+ * Constructs a \bernoulli_distribution object.
+ * p is the parameter of the distribution.
+ *
+ * Requires: 0 <= p <= 1
+ */
explicit bernoulli_distribution(const RealType& p_arg = RealType(0.5))
: _p(p_arg)
{
@@ -42,9 +53,20 @@
// compiler-generated copy ctor and assignment operator are fine
+ /**
+ * Returns: The "p" parameter of the distribution.
+ */
RealType p() const { return _p; }
+ /**
+ * Effects: Subsequent uses of the distribution do not depend
+ * on values produced by any engine prior to invoking reset.
+ */
void reset() { }
+ /**
+ * Returns: a random variate distributed according to the
+ * \bernoulli_distribution.
+ */
template<class Engine>
result_type operator()(Engine& eng)
{
@@ -55,6 +77,9 @@
}
#ifndef BOOST_RANDOM_NO_STREAM_OPERATORS
+ /**
+ * Writes the parameters of the distribution to a @c std::ostream.
+ */
template<class CharT, class Traits>
friend std::basic_ostream<CharT,Traits>&
operator<<(std::basic_ostream<CharT,Traits>& os, const bernoulli_distribution& bd)
@@ -63,6 +88,9 @@
return os;
}
+ /**
+ * Reads the parameters of the distribution from a @c std::istream.
+ */
template<class CharT, class Traits>
friend std::basic_istream<CharT,Traits>&
operator>>(std::basic_istream<CharT,Traits>& is, bernoulli_distribution& bd)
Modified: trunk/boost/random/binomial_distribution.hpp
==============================================================================
--- trunk/boost/random/binomial_distribution.hpp (original)
+++ trunk/boost/random/binomial_distribution.hpp 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -21,7 +21,14 @@
namespace boost {
-// Knuth
+/**
+ * The binomial distribution is an integer valued distribution with
+ * two parameters, @c t and @c p. The values of the distribution
+ * are within the range [0,t].
+ *
+ * The probability that the distribution produces a value k is
+ * \f${t \choose k}p^k(1-p)^{t-k}\f$.
+ */
template<class IntType = int, class RealType = double>
class binomial_distribution
{
@@ -29,20 +36,36 @@
typedef typename bernoulli_distribution<RealType>::input_type input_type;
typedef IntType result_type;
- explicit binomial_distribution(IntType t_arg = 1,
- const RealType& p_arg = RealType(0.5))
- : _bernoulli(p_arg), _t(t_arg)
+ /**
+ * Construct an @c binomial_distribution object. @c t and @c p
+ * are the parameters of the distribution.
+ *
+ * Requires: t >=0 && 0 <= p <= 1
+ */
+ explicit binomial_distribution(IntType t = 1,
+ const RealType& p = RealType(0.5))
+ : _bernoulli(p), _t(t)
{
assert(_t >= 0);
- assert(RealType(0) <= p_arg && p_arg <= RealType(1));
+ assert(RealType(0) <= p && p <= RealType(1));
}
// compiler-generated copy ctor and assignment operator are fine
+ /** Returns: the @c t parameter of the distribution */
IntType t() const { return _t; }
+ /** Returns: the @c p parameter of the distribution */
RealType p() const { return _bernoulli.p(); }
+ /**
+ * Effects: Subsequent uses of the distribution do not depend
+ * on values produced by any engine prior to invoking reset.
+ */
void reset() { }
+ /**
+ * Returns: a random variate distributed according to the
+ * binomial distribution.
+ */
template<class Engine>
result_type operator()(Engine& eng)
{
@@ -55,6 +78,9 @@
}
#ifndef BOOST_RANDOM_NO_STREAM_OPERATORS
+ /**
+ * Writes the parameters of the distribution to a @c std::ostream.
+ */
template<class CharT, class Traits>
friend std::basic_ostream<CharT,Traits>&
operator<<(std::basic_ostream<CharT,Traits>& os, const binomial_distribution& bd)
@@ -63,6 +89,9 @@
return os;
}
+ /**
+ * Reads the parameters of the distribution from a @c std::istream.
+ */
template<class CharT, class Traits>
friend std::basic_istream<CharT,Traits>&
operator>>(std::basic_istream<CharT,Traits>& is, binomial_distribution& bd)
Modified: trunk/boost/random/cauchy_distribution.hpp
==============================================================================
--- trunk/boost/random/cauchy_distribution.hpp (original)
+++ trunk/boost/random/cauchy_distribution.hpp 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -30,7 +30,14 @@
using std::tan;
#endif
-// Cauchy distribution: p(x) = sigma/(pi*(sigma**2 + (x-median)**2))
+// Cauchy distribution:
+
+/**
+ * The cauchy distribution is a continuous distribution with two
+ * parameters, sigma and median.
+ *
+ * It has \f$p(x) = \frac{\sigma}{\pi(\sigma^2 + (x-m)^2)}\f$
+ */
template<class RealType = double>
class cauchy_distribution
{
@@ -42,16 +49,34 @@
BOOST_STATIC_ASSERT(!std::numeric_limits<RealType>::is_integer);
#endif
+ /**
+ * Constructs a \cauchy_distribution with the paramters @c median
+ * and @c sigma.
+ */
explicit cauchy_distribution(result_type median_arg = result_type(0),
result_type sigma_arg = result_type(1))
: _median(median_arg), _sigma(sigma_arg) { }
// compiler-generated copy ctor and assignment operator are fine
+ /**
+ * Returns: the "median" parameter of the distribution
+ */
result_type median() const { return _median; }
+ /**
+ * Returns: the "sigma" parameter of the distribution
+ */
result_type sigma() const { return _sigma; }
+ /**
+ * Effects: Subsequent uses of the distribution do not depend
+ * on values produced by any engine prior to invoking reset.
+ */
void reset() { }
+ /**
+ * Returns: A random variate distributed according to the
+ * cauchy distribution.
+ */
template<class Engine>
result_type operator()(Engine& eng)
{
@@ -64,6 +89,9 @@
}
#ifndef BOOST_RANDOM_NO_STREAM_OPERATORS
+ /**
+ * Writes the parameters of the distribution to a @c std::ostream.
+ */
template<class CharT, class Traits>
friend std::basic_ostream<CharT,Traits>&
operator<<(std::basic_ostream<CharT,Traits>& os, const cauchy_distribution& cd)
@@ -72,6 +100,9 @@
return os;
}
+ /**
+ * Reads the parameters of the distribution from a @c std::istream.
+ */
template<class CharT, class Traits>
friend std::basic_istream<CharT,Traits>&
operator>>(std::basic_istream<CharT,Traits>& is, cauchy_distribution& cd)
Modified: trunk/boost/random/discard_block.hpp
==============================================================================
--- trunk/boost/random/discard_block.hpp (original)
+++ trunk/boost/random/discard_block.hpp 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -26,6 +26,15 @@
namespace boost {
namespace random {
+/**
+ * The class template \discard_block is a model of
+ * \pseudo_random_number_generator. It modifies
+ * another generator by discarding parts of its output.
+ * Out of every block of @c r results, the first @c p
+ * will be returned and the rest discarded.
+ *
+ * Requires: 0 < p <= r
+ */
template<class UniformRandomNumberGenerator, unsigned int p, unsigned int r>
class discard_block
{
Modified: trunk/boost/random/exponential_distribution.hpp
==============================================================================
--- trunk/boost/random/exponential_distribution.hpp (original)
+++ trunk/boost/random/exponential_distribution.hpp 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -25,7 +25,11 @@
namespace boost {
-// exponential distribution: p(x) = lambda * exp(-lambda * x)
+/**
+ * The exponential distribution has a single parameter lambda.
+ *
+ * It has \f$p(x) = \lambda e^{-\lambda x}\f$
+ */
template<class RealType = double>
class exponential_distribution
{
Modified: trunk/boost/random/gamma_distribution.hpp
==============================================================================
--- trunk/boost/random/gamma_distribution.hpp (original)
+++ trunk/boost/random/gamma_distribution.hpp 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -23,7 +23,14 @@
namespace boost {
-// Knuth
+// The algorithm is taken from Knuth
+
+/**
+ * The gamma distribution is a continuous distribution with a single
+ * parameter alpha.
+ *
+ * It has \f$p(x) = x^{\alpha-1}\frac{e^{-x}}{\Gamma(\alpha)}\f$.
+ */
template<class RealType = double>
class gamma_distribution
{
@@ -114,6 +121,7 @@
#endif
private:
+ /// \cond hide_private_members
void init()
{
#ifndef BOOST_NO_STDC_NAMESPACE
@@ -122,6 +130,7 @@
#endif
_p = exp(result_type(1)) / (_alpha + exp(result_type(1)));
}
+ /// \endcond
exponential_distribution<RealType> _exp;
result_type _alpha;
Modified: trunk/boost/random/geometric_distribution.hpp
==============================================================================
--- trunk/boost/random/geometric_distribution.hpp (original)
+++ trunk/boost/random/geometric_distribution.hpp 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -30,7 +30,14 @@
using std::log;
#endif
-// geometric distribution: p(i) = (1-p) * pow(p, i-1) (integer)
+/**
+ * An instantiation of the class template @c geometric_distribution models
+ * a \random_distribution. The distribution produces positive
+ * integers which are the number of bernoulli trials
+ * with probability @c p required to get one that fails.
+ *
+ * For the geometric distribution, \f$p(i) = (1-p) p^{i-1}\f$.
+ */
template<class IntType = int, class RealType = double>
class geometric_distribution
{
@@ -38,8 +45,13 @@
typedef RealType input_type;
typedef IntType result_type;
- explicit geometric_distribution(const RealType& p_arg = RealType(0.5))
- : _p(p_arg)
+ /**
+ * Contructs a new geometric_distribution with the paramter @c p.
+ *
+ * Requires: 0 < p < 1
+ */
+ explicit geometric_distribution(const RealType& p = RealType(0.5))
+ : _p(p)
{
assert(RealType(0) < _p && _p < RealType(1));
init();
@@ -47,6 +59,9 @@
// compiler-generated copy ctor and assignment operator are fine
+ /**
+ * Returns: the distribution parameter @c p
+ */
RealType p() const { return _p; }
void reset() { }
@@ -80,6 +95,9 @@
#endif
private:
+
+ /// \cond hide_private_functions
+
void init()
{
#ifndef BOOST_NO_STDC_NAMESPACE
@@ -88,6 +106,8 @@
_log_p = log(_p);
}
+ /// \endcond
+
RealType _p;
RealType _log_p;
};
Modified: trunk/boost/random/inversive_congruential.hpp
==============================================================================
--- trunk/boost/random/inversive_congruential.hpp (original)
+++ trunk/boost/random/inversive_congruential.hpp 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -28,6 +28,35 @@
namespace random {
// Eichenauer and Lehn 1986
+/**
+ * Instantiations of class template @c inversive_congruential model a
+ * \pseudo_random_number_generator. It uses the inversive congruential
+ * algorithm (ICG) described in
+ *
+ * @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. ftp://random.mat.sbg.ac.at/pub/data/wsc95.ps
+ * @endblockquote
+ *
+ * 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.
+ *
+ * The template parameter IntType 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.
+ *
+ * @xmlnote
+ * 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"performance"). However,
+ * the paper talks of only 3x slowdown, so the Euclidian Algorithm is probably
+ * not optimal for calculating the multiplicative inverse.
+ * @endxmlnote
+ */
template<class IntType, IntType a, IntType b, IntType p, IntType val>
class inversive_congruential
{
@@ -47,6 +76,10 @@
result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return b == 0 ? 1 : 0; }
result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return p-1; }
+ /**
+ * Constructs an inversive_congruential generator with
+ * @c y0 as the initial state.
+ */
explicit inversive_congruential(IntType y0 = 1) : value(y0)
{
BOOST_STATIC_ASSERT(b >= 0);
@@ -58,6 +91,7 @@
template<class It> inversive_congruential(It& first, It last)
{ seed(first, last); }
+ /** Changes the current state to y0. */
void seed(IntType y0 = 1) { value = y0; if(b == 0) assert(y0 > 0); }
template<class It> void seed(It& first, It last)
{
@@ -121,6 +155,16 @@
} // namespace random
+/**
+ * The specialization hellekalek1995 was suggested in
+ *
+ * @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. ftp://random.mat.sbg.ac.at/pub/data/wsc95.ps
+ * @endblockquote
+ */
typedef random::inversive_congruential<int32_t, 9102, 2147483647-36884165,
2147483647, 0> hellekalek1995;
Modified: trunk/boost/random/lagged_fibonacci.hpp
==============================================================================
--- trunk/boost/random/lagged_fibonacci.hpp (original)
+++ trunk/boost/random/lagged_fibonacci.hpp 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -80,6 +80,12 @@
}
# endif
+/**
+ * Instantiations of class template \lagged_fibonacci model a
+ * \pseudo_random_number_generator. It uses a lagged Fibonacci
+ * algorithm with two lags @c p and @c q:
+ * x(i) = x(i-p) + x(i-q) (mod 2<sup>w</sup>) with p > q.
+ */
template<class UIntType, int w, unsigned int p, unsigned int q,
UIntType val = 0>
class lagged_fibonacci
@@ -91,24 +97,45 @@
BOOST_STATIC_CONSTANT(unsigned int, long_lag = p);
BOOST_STATIC_CONSTANT(unsigned int, short_lag = q);
+ /**
+ * Returns: the smallest value that the generator can produce
+ */
result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return 0; }
+ /**
+ * Returns: the largest value that the generator can produce
+ */
result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return wordmask; }
+ /**
+ * Creates a new @c lagged_fibonacci generator and calls @c seed()
+ */
lagged_fibonacci() { init_wordmask(); seed(); }
+ /**
+ * Creates a new @c lagged_fibonacci generator and calls @c seed(value)
+ */
explicit lagged_fibonacci(uint32_t value) { init_wordmask(); seed(value); }
+ /**
+ * Creates a new @c lagged_fibonacci generator and calls @c seed(first, last)
+ */
template<class It> lagged_fibonacci(It& first, It last)
{ init_wordmask(); seed(first, last); }
// compiler-generated copy ctor and assignment operator are fine
private:
+ /// \cond hide_private_members
void init_wordmask()
{
wordmask = 0;
for(int j = 0; j < w; ++j)
wordmask |= (1u << j);
}
+ /// \endcond
public:
+ /**
+ * Sets the state of the generator to values produced by
+ * a \minstd_rand generator.
+ */
void seed(uint32_t value = 331u)
{
minstd_rand0 gen(value);
@@ -117,6 +144,11 @@
i = long_lag;
}
+ /**
+ * Sets the state of the generator to values from the iterator
+ * range [first, last). If there are not enough elements in the
+ * range [first, last) throws @c std::invalid_argument.
+ */
template<class It>
void seed(It& first, It last)
{
@@ -129,6 +161,9 @@
throw std::invalid_argument("lagged_fibonacci::seed");
}
+ /**
+ * Returns: the next value of the generator
+ */
result_type operator()()
{
if(i >= long_lag)
@@ -183,7 +218,10 @@
#endif
private:
+ /// \cond hide_private_members
void fill();
+ /// \endcond
+
UIntType wordmask;
unsigned int i;
UIntType x[long_lag];
@@ -199,6 +237,8 @@
const unsigned int lagged_fibonacci<UIntType, w, p, q, val>::short_lag;
#endif
+/// \cond hide_private_members
+
template<class UIntType, int w, unsigned int p, unsigned int q, UIntType val>
void lagged_fibonacci<UIntType, w, p, q, val>::fill()
{
@@ -257,6 +297,30 @@
#undef BOOST_RANDOM_FIBONACCI_VAL
+/// \endcond
+
+/**
+ * Instantiations of class template @c lagged_fibonacci_01 model a
+ * \pseudo_random_number_generator. It uses a lagged Fibonacci
+ * algorithm with two lags @c p and @c q, evaluated in floating-point
+ * arithmetic: x(i) = x(i-p) + x(i-q) (mod 1) with p > q. See
+ *
+ * @blockquote
+ * "Uniform random number generators for supercomputers", Richard Brent,
+ * Proc. of Fifth Australian Supercomputer Conference, Melbourne,
+ * Dec. 1992, pp. 704-706.
+ * @endblockquote
+ *
+ * @xmlnote
+ * 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 \lagged_fibonacci607 instead.
+ * @endxmlnote
+ *
+ * The generator requires considerable amounts of memory for the storage
+ * of its state array. For example, \lagged_fibonacci607 requires about
+ * 4856 bytes and \lagged_fibonacci44497 requires about 350 KBytes.
+ */
template<class RealType, int w, unsigned int p, unsigned int q>
class lagged_fibonacci_01
{
@@ -267,9 +331,12 @@
BOOST_STATIC_CONSTANT(unsigned int, long_lag = p);
BOOST_STATIC_CONSTANT(unsigned int, short_lag = q);
+ /** Constructs a @c lagged_fibonacci_01 generator and calls @c seed(). */
lagged_fibonacci_01() { init_modulus(); seed(); }
+ /** Constructs a @c lagged_fibonacci_01 generator and calls @c seed(value). */
BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(lagged_fibonacci_01, uint32_t, value)
{ init_modulus(); seed(value); }
+ /** Constructs a @c lagged_fibonacci_01 generator and calls @c seed(gen). */
BOOST_RANDOM_DETAIL_GENERATOR_CONSTRUCTOR(lagged_fibonacci_01, Generator, gen)
{ init_modulus(); seed(gen); }
template<class It> lagged_fibonacci_01(It& first, It last)
@@ -277,6 +344,7 @@
// compiler-generated copy ctor and assignment operator are fine
private:
+ /// \cond hide_private_members
void init_modulus()
{
#ifndef BOOST_NO_STDC_NAMESPACE
@@ -285,18 +353,30 @@
#endif
_modulus = pow(RealType(2), word_size);
}
+ /// \endcond
public:
+ /** Calls seed(331u). */
void seed() { seed(331u); }
+ /**
+ * Constructs a \minstd_rand0 generator with the constructor parameter
+ * value and calls seed 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.
+ */
BOOST_RANDOM_DETAIL_ARITHMETIC_SEED(lagged_fibonacci_01, uint32_t, value)
{
minstd_rand0 intgen(value);
seed(intgen);
}
- // For GCC, moving this function out-of-line prevents inlining, which may
- // reduce overall object code size. However, MSVC does not grok
- // out-of-line template member functions.
+ /**
+ * Sets the state of this @c lagged_fibonacci_01 to the values returned
+ * by p invocations of \uniform_01<code>\<RealType\>()(gen)</code>.
+ *
+ * Complexity: Exactly p invocations of gen.
+ */
BOOST_RANDOM_DETAIL_GENERATOR_SEED(lagged_fibonacci, Generator, gen)
{
// use pass-by-reference, but wrap argument in pass_through_engine
@@ -407,7 +487,9 @@
#endif
private:
+ /// \cond hide_private_members
void fill();
+ /// \endcond
unsigned int i;
RealType x[long_lag];
RealType _modulus;
@@ -426,6 +508,7 @@
#endif
+/// \cond hide_private_members
template<class RealType, int w, unsigned int p, unsigned int q>
void lagged_fibonacci_01<RealType, w, p, q>::fill()
{
@@ -446,17 +529,70 @@
}
i = 0;
}
+/// \endcond
} // namespace random
+#ifdef BOOST_RANDOM_DOXYGEN
+namespace detail {
+/**
+ * The specializations lagged_fibonacci607 ... lagged_fibonacci44497
+ * use well tested lags.
+ *
+ * See
+ *
+ * @blockquote
+ * "On the Periods of Generalized Fibonacci Recurrences", Richard P. Brent
+ * Computer Sciences Laboratory Australian National University, December 1992
+ * @endblockquote
+ *
+ * The lags used here can be found in
+ *
+ * @blockquote
+ * "Uniform random number generators for supercomputers", Richard Brent,
+ * Proc. of Fifth Australian Supercomputer Conference, Melbourne,
+ * Dec. 1992, pp. 704-706.
+ * @endblockquote
+ */
+struct lagged_fibonacci_doc {};
+}
+#endif
+
+/**
+ * @copydoc boost::detail::lagged_fibonacci_doc
+ */
typedef random::lagged_fibonacci_01<double, 48, 607, 273> lagged_fibonacci607;
+/**
+ * @copydoc boost::detail::lagged_fibonacci_doc
+ */
typedef random::lagged_fibonacci_01<double, 48, 1279, 418> lagged_fibonacci1279;
+/**
+ * @copydoc boost::detail::lagged_fibonacci_doc
+ */
typedef random::lagged_fibonacci_01<double, 48, 2281, 1252> lagged_fibonacci2281;
+/**
+ * @copydoc boost::detail::lagged_fibonacci_doc
+ */
typedef random::lagged_fibonacci_01<double, 48, 3217, 576> lagged_fibonacci3217;
+/**
+ * @copydoc boost::detail::lagged_fibonacci_doc
+ */
typedef random::lagged_fibonacci_01<double, 48, 4423, 2098> lagged_fibonacci4423;
+/**
+ * @copydoc boost::detail::lagged_fibonacci_doc
+ */
typedef random::lagged_fibonacci_01<double, 48, 9689, 5502> lagged_fibonacci9689;
+/**
+ * @copydoc boost::detail::lagged_fibonacci_doc
+ */
typedef random::lagged_fibonacci_01<double, 48, 19937, 9842> lagged_fibonacci19937;
+/**
+ * @copydoc boost::detail::lagged_fibonacci_doc
+ */
typedef random::lagged_fibonacci_01<double, 48, 23209, 13470> lagged_fibonacci23209;
+/**
+ * @copydoc boost::detail::lagged_fibonacci_doc
+ */
typedef random::lagged_fibonacci_01<double, 48, 44497, 21034> lagged_fibonacci44497;
Modified: trunk/boost/random/linear_congruential.hpp
==============================================================================
--- trunk/boost/random/linear_congruential.hpp (original)
+++ trunk/boost/random/linear_congruential.hpp 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -31,7 +31,26 @@
namespace boost {
namespace random {
-// compile-time configurable linear congruential generator
+/**
+ * Instantiations of class template linear_congruential model a
+ * \pseudo_random_number_generator. Linear congruential pseudo-random
+ * number generators are described in:
+ *
+ * "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
+ *
+ * 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 IntType 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.
+ *
+ * Note: 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 minstd_rand instead.
+ */
template<class IntType, IntType a, IntType c, IntType m, IntType val>
class linear_congruential
{
@@ -53,6 +72,9 @@
// BOOST_STATIC_ASSERT(m == 0 || a < m);
// BOOST_STATIC_ASSERT(m == 0 || c < m);
+ /**
+ * Constructs a linear_congruential generator, seeding it with @c x0.
+ */
explicit linear_congruential(IntType x0 = 1)
{
seed(x0);
@@ -63,6 +85,14 @@
#endif
}
+ /**
+ * Constructs a @c linear_congruential generator and seeds it
+ * with values taken from the itrator range [first, last)
+ * and adjusts first to point to the element after the last one
+ * used. If there are not enough elements, throws @c std::invalid_argument.
+ *
+ * first and last must be input iterators.
+ */
template<class It>
linear_congruential(It& first, It last)
{
@@ -70,6 +100,13 @@
}
// compiler-generated copy constructor and assignment operator are fine
+
+ /**
+ * If c mod m is zero and x0 mod m is zero, changes the current value of
+ * the generator to 1. Otherwise, changes it to x0 mod m. If c is zero,
+ * distinct seeds in the range [1,m) will leave the generator in distinct
+ * states. If c is not zero, the range is [0,m).
+ */
void seed(IntType x0 = 1)
{
// wrap _x if it doesn't fit in the destination
@@ -90,6 +127,14 @@
assert(_x <= (max)());
}
+ /**
+ * seeds a @c linear_congruential generator with values taken
+ * from the itrator range [first, last) and adjusts @c first to
+ * point to the element after the last one used. If there are
+ * not enough elements, throws @c std::invalid_argument.
+ *
+ * @c first and @c last must be input iterators.
+ */
template<class It>
void seed(It& first, It last)
{
@@ -98,9 +143,18 @@
seed(*first++);
}
+ /**
+ * Returns the smallest value that the @c linear_congruential generator
+ * can produce.
+ */
result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return c == 0 ? 1 : 0; }
+ /**
+ * Returns the largest value that the @c linear_congruential generator
+ * can produce.
+ */
result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return modulus-1; }
+ /** Returns the next value of the @c linear_congruential generator. */
IntType operator()()
{
_x = const_mod<IntType, m>::mult_add(a, _x, c);
@@ -199,14 +253,48 @@
} // namespace random
// validation values from the publications
+/**
+ * The specialization \minstd_rand0 was originally suggested in
+ *
+ * @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
+ * @endblockquote
+ *
+ * It is examined more closely together with \minstd_rand 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
+ * @endblockquote
+ */
typedef random::linear_congruential<int32_t, 16807, 0, 2147483647,
1043618065> minstd_rand0;
+
+/** The specialization \minstd_rand was suggested 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
+ * @endblockquote
+ */
typedef random::linear_congruential<int32_t, 48271, 0, 2147483647,
399268537> minstd_rand;
#if !defined(BOOST_NO_INT64_T) && !defined(BOOST_NO_INTEGRAL_INT64_T)
-// emulate the lrand48() C library function; requires support for uint64_t
+/** Class @c rand48 models a \pseudo_random_number_generator. It uses
+ * the linear congruential algorithm with the parameters a = 0x5DEECE66D,
+ * c = 0xB, m = 2**48. It delivers identical results to the @c lrand48()
+ * function available on some systems (assuming lcong48 has not been called).
+ *
+ * It is only available on systems where @c uint64_t is provided as an
+ * integral type, so that for example static in-class constants and/or
+ * enum definitions with large @c uint64_t numbers work.
+ */
class rand48
{
public:
@@ -218,17 +306,46 @@
#else
enum { has_fixed_range = false };
#endif
+ /**
+ * Returns the smallest value that the generator can produce
+ */
int32_t min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return 0; }
+ /**
+ * Returns the largest value that the generator can produce
+ */
int32_t max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return std::numeric_limits<int32_t>::max BOOST_PREVENT_MACRO_SUBSTITUTION (); }
+#ifdef BOOST_RANDOM_DOXYGEN
+ /**
+ * If T is an integral type smaller than int46_t, constructs
+ * a \rand48 generator with x(0) := (x0 << 16) | 0x330e. Otherwise
+ * constructs a \rand48 generator with x(0) = x0.
+ */
+ template<class T> explicit rand48(T x0 = 1);
+#else
rand48() : lcf(cnv(static_cast<int32_t>(1))) {}
template<class T> explicit rand48(T x0) : lcf(cnv(x0)) { }
+#endif
template<class It> rand48(It& first, It last) : lcf(first, last) { }
+
// compiler-generated copy ctor and assignment operator are fine
+
+#ifdef BOOST_RANDOM_DOXYGEN
+ /**
+ * If T is an integral type smaller than int46_t, changes
+ * the current value x(n) of the generator to (x0 << 16) | 0x330e.
+ * Otherwise changes the current value x(n) to x0.
+ */
+ template<class T> void seed(T x0 = 1);
+#else
void seed() { seed(static_cast<int32_t>(1)); }
template<class T> void seed(T x0) { lcf.seed(cnv(x0)); }
+#endif
template<class It> void seed(It& first, It last) { lcf.seed(first,last); }
+ /**
+ * Returns the next value of the generator.
+ */
int32_t operator()() { return static_cast<int32_t>(lcf() >> 17); }
// by experiment from lrand48()
static bool validation(int32_t x) { return x == 1993516219; }
@@ -259,6 +376,7 @@
{ return !(*this == rhs); }
#endif
private:
+ /// \cond hide_private_members
random::linear_congruential<uint64_t,
uint64_t(0xDEECE66DUL) | (uint64_t(0x5) << 32), // xxxxULL is not portable
0xB, uint64_t(1)<<48, /* unknown */ 0> lcf;
@@ -274,6 +392,7 @@
static uint64_t cnv(float x) { return(static_cast<uint64_t>(x)); }
static uint64_t cnv(double x) { return(static_cast<uint64_t>(x)); }
static uint64_t cnv(long double x) { return(static_cast<uint64_t>(x)); }
+ /// \endcond
};
#endif /* !BOOST_NO_INT64_T && !BOOST_NO_INTEGRAL_INT64_T */
Modified: trunk/boost/random/linear_feedback_shift.hpp
==============================================================================
--- trunk/boost/random/linear_feedback_shift.hpp (original)
+++ trunk/boost/random/linear_feedback_shift.hpp 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -25,7 +25,16 @@
namespace boost {
namespace random {
-// Tausworte 1965
+/**
+ * Instatiation of @c linear_feedback_shift model a
+ * \pseudo_random_number_generator. It was originally
+ * proposed in
+ *
+ * @blockquote
+ * "Random numbers generated by linear recurrence modulo two.",
+ * Tausworthe, R. C.(1965), Mathematics of Computation 19, 201-209.
+ * @endblockquote
+ */
template<class UIntType, int w, int k, int q, int s, UIntType val>
class linear_feedback_shift
{
Modified: trunk/boost/random/lognormal_distribution.hpp
==============================================================================
--- trunk/boost/random/lognormal_distribution.hpp (original)
+++ trunk/boost/random/lognormal_distribution.hpp 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -40,6 +40,13 @@
using std::exp;
#endif
+/**
+ * Instantiations of class template lognormal_distribution model a
+ * \random_distribution. Such a distribution produces random numbers
+ * with \f$p(x) = \frac{1}{x \sigma_N \sqrt{2\pi}} e^{\frac{-\left(\log(x)-\mu_N\right)^2}{2\sigma_N^2}}\f$
+ * for x > 0, where \f$\mu_N = \log\left(\frac{\mu^2}{\sqrt{\sigma^2 + \mu^2}}\right)\f$ and
+ * \f$\sigma_N = \sqrt{\log\left(1 + \frac{\sigma^2}{\mu^2}\right)}\f$.
+ */
template<class RealType = double>
class lognormal_distribution
{
@@ -51,6 +58,10 @@
BOOST_STATIC_ASSERT(!std::numeric_limits<RealType>::is_integer);
#endif
+ /**
+ * Constructs a lognormal_distribution. @c mean and @c sigma are the
+ * mean and standard deviation of the lognormal distribution.
+ */
explicit lognormal_distribution(result_type mean_arg = result_type(1),
result_type sigma_arg = result_type(1))
: _mean(mean_arg), _sigma(sigma_arg)
@@ -95,6 +106,8 @@
#endif
private:
+
+ /// \cond hide_private_members
void init()
{
#ifndef BOOST_NO_STDC_NAMESPACE
@@ -104,6 +117,7 @@
_nmean = log(_mean*_mean/sqrt(_sigma*_sigma + _mean*_mean));
_nsigma = sqrt(log(_sigma*_sigma/_mean/_mean+result_type(1)));
}
+ /// \endcond
RealType _mean, _sigma;
RealType _nmean, _nsigma;
Modified: trunk/boost/random/mersenne_twister.hpp
==============================================================================
--- trunk/boost/random/mersenne_twister.hpp (original)
+++ trunk/boost/random/mersenne_twister.hpp 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -33,7 +33,34 @@
namespace boost {
namespace random {
-// http://www.math.keio.ac.jp/matumoto/emt.html
+/**
+ * Instantiations of class template mersenne_twister model a
+ * \pseudo_random_number_generator. It uses the algorithm described in
+ *
+ * @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.
+ * @endblockquote
+ *
+ * @xmlnote
+ * 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.
+ * @endxmlnote
+ *
+ * The seeding from an integer was changed in April 2005 to address a
+ * weakness.
+ *
+ * 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 \mt19937 instead.
+ *
+ * The generator requires considerable amounts of memory for the storage of
+ * its state array. For example, \mt11213b requires about 1408 bytes and
+ * \mt19937 requires about 2496 bytes.
+ */
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 mersenne_twister
@@ -54,19 +81,39 @@
BOOST_STATIC_CONSTANT(bool, has_fixed_range = false);
+ /**
+ * Constructs a @c mersenne_twister and calls @c seed().
+ */
mersenne_twister() { seed(); }
+ /**
+ * Constructs a @c mersenne_twister and calls @c seed(value).
+ */
BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(mersenne_twister, UIntType, value)
{ seed(value); }
template<class It> mersenne_twister(It& first, It last) { seed(first,last); }
+ /**
+ * Constructs a mersenne_twister and calls @c seed(gen).
+ *
+ * @xmlnote
+ * The copy constructor will always be preferred over
+ * the templated constructor.
+ * @endxmlnote
+ */
BOOST_RANDOM_DETAIL_GENERATOR_CONSTRUCTOR(mersenne_twister, Generator, gen)
{ seed(gen); }
// compiler-generated copy ctor and assignment operator are fine
+ /** Calls @c seed(result_type(5489)). */
void seed() { seed(UIntType(5489)); }
+ /**
+ * Sets the state x(0) to v mod 2w. Then, iteratively,
+ * sets x(i) to (i + 1812433253 * (x(i-1) xor (x(i-1) rshift w-2))) mod 2<sup>w</sup>
+ * for i = 1 .. n-1. x(n) is the first value to be returned by operator().
+ */
BOOST_RANDOM_DETAIL_ARITHMETIC_SEED(mersenne_twister, UIntType, value)
{
// New seeding algorithm from
@@ -81,9 +128,12 @@
}
}
- // For GCC, moving this function out-of-line prevents inlining, which may
- // reduce overall object code size. However, MSVC does not grok
- // out-of-line definitions of member function templates.
+ /**
+ * Sets the state of this mersenne_twister to the values
+ * returned by n invocations of gen.
+ *
+ * Complexity: Exactly n invocations of gen.
+ */
BOOST_RANDOM_DETAIL_GENERATOR_SEED(mersenne_twister, Generator, gen)
{
#ifndef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS
@@ -170,6 +220,7 @@
#endif
private:
+ /// \cond hide_private_members
// returns x(i-n+index), where index is in 0..n-1
UIntType compute(unsigned int index) const
{
@@ -177,6 +228,7 @@
return x[ (i + n + index) % (2*n) ];
}
void twist(int block);
+ /// \endcond
// state representation: next output is o(x(i))
// x[0] ... x[k] x[k+1] ... x[n-1] x[n] ... x[2*n-1] represents
@@ -225,6 +277,7 @@
const int mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::output_l;
#endif
+/// \cond hide_private_members
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>
void mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::twist(int block)
@@ -256,6 +309,7 @@
i = 0;
}
}
+/// \endcond
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>
@@ -278,11 +332,31 @@
} // namespace random
-
+/**
+ * The specializations \mt11213b and \mt19937 are from
+ *
+ * @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.
+ * @endblockquote
+ */
typedef random::mersenne_twister<uint32_t,32,351,175,19,0xccab8ee7,11,
7,0x31b6ab00,15,0xffe50000,17, 0xa37d3c92> mt11213b;
-// validation by experiment from mt19937.c
+/**
+ * The specializations \mt11213b and \mt19937 are from
+ *
+ * @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.
+ * @endblockquote
+ */
typedef random::mersenne_twister<uint32_t,32,624,397,31,0x9908b0df,11,
7,0x9d2c5680,15,0xefc60000,18, 3346425566U> mt19937;
Modified: trunk/boost/random/normal_distribution.hpp
==============================================================================
--- trunk/boost/random/normal_distribution.hpp (original)
+++ trunk/boost/random/normal_distribution.hpp 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -25,6 +25,13 @@
namespace boost {
+/**
+ * Instantiations of class template normal_distribution model a
+ * \random_distribution. Such a distribution produces random numbers
+ * @c x distributed with probability density function
+ * \f$p(x) = \frac{1}{\sqrt{2\pi\sigma}} e^{-\frac{(x-\mu)^2}{2\sigma^2}}\f$,
+ * where mean and sigma are the parameters of the distribution.
+ */
// deterministic Box-Muller method, uses trigonometric functions
template<class RealType = double>
class normal_distribution
@@ -37,6 +44,12 @@
BOOST_STATIC_ASSERT(!std::numeric_limits<RealType>::is_integer);
#endif
+ /**
+ * Constructs a normal_distribution object. @c mean and @c sigma are
+ * the parameters for the distribution.
+ *
+ * Requires: sigma > 0
+ */
explicit normal_distribution(const result_type& mean_arg = result_type(0),
const result_type& sigma_arg = result_type(1))
: _mean(mean_arg), _sigma(sigma_arg), _valid(false)
@@ -52,7 +65,13 @@
// compiler-generated copy ctor and assignment operator are fine
+ /**
+ * Returns: The "mean" parameter of the distribution.
+ */
RealType mean() const { return _mean; }
+ /**
+ * Returns: The "sigma" parameter of the distribution.
+ */
RealType sigma() const { return _sigma; }
void reset() { _valid = false; }
Modified: trunk/boost/random/poisson_distribution.hpp
==============================================================================
--- trunk/boost/random/poisson_distribution.hpp (original)
+++ trunk/boost/random/poisson_distribution.hpp 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -24,6 +24,12 @@
namespace boost {
// Knuth
+
+/**
+ * An instantiation of the class template @c poisson_distribution is a
+ * model of \random_distribution. The poisson distribution has
+ * \f$p(i) = \frac{e^{-\lambda}\lambda^i}{i!}\f$
+ */
template<class IntType = int, class RealType = double>
class poisson_distribution
{
@@ -31,6 +37,11 @@
typedef RealType input_type;
typedef IntType result_type;
+ /**
+ * Constructs a @c poisson_distribution with the parameter @c mean.
+ *
+ * Requires: mean > 0
+ */
explicit poisson_distribution(const RealType& mean_arg = RealType(1))
: _mean(mean_arg)
{
@@ -46,6 +57,9 @@
// compiler-generated copy ctor and assignment operator are fine
+ /**
+ * Returns: the "mean" parameter of the distribution.
+ */
RealType mean() const { return _mean; }
void reset() { }
@@ -81,6 +95,7 @@
#endif
private:
+ /// \cond hide_private_members
void init()
{
#ifndef BOOST_NO_STDC_NAMESPACE
@@ -89,6 +104,7 @@
#endif
_exp_mean = exp(-_mean);
}
+ /// \endcond
RealType _mean;
// some precomputed data from the parameters
Modified: trunk/boost/random/random_number_generator.hpp
==============================================================================
--- trunk/boost/random/random_number_generator.hpp (original)
+++ trunk/boost/random/random_number_generator.hpp 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -24,7 +24,14 @@
namespace boost {
-// a model for RandomNumberGenerator std:25.2.11 [lib.alg.random.shuffle]
+/**
+ * Instantiations of class template random_number_generator model a
+ * RandomNumberGenerator (std:25.2.11 [lib.alg.random.shuffle]). On
+ * each invocation, it returns a uniformly distributed integer in
+ * the range [0..n).
+ *
+ * The template parameter IntType shall denote some integer-like value type.
+ */
template<class UniformRandomNumberGenerator, class IntType = long>
class random_number_generator
{
@@ -32,6 +39,11 @@
typedef UniformRandomNumberGenerator base_type;
typedef IntType argument_type;
typedef IntType result_type;
+ /**
+ * Constructs a random_number_generator functor with the given
+ * \uniform_random_number_generator as the underlying source of
+ * random numbers.
+ */
random_number_generator(base_type& rng) : _rng(rng)
{
#ifndef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS
@@ -41,6 +53,9 @@
// compiler-generated copy ctor is fine
// assignment is disallowed because there is a reference member
+ /**
+ * Returns a value in the range [0, n)
+ */
result_type operator()(argument_type n)
{
typedef uniform_int<IntType> dist_type;
Modified: trunk/boost/random/ranlux.hpp
==============================================================================
--- trunk/boost/random/ranlux.hpp (original)
+++ trunk/boost/random/ranlux.hpp 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -28,20 +28,51 @@
typedef subtract_with_carry_01<double, 48, 10, 24> ranlux64_base_01;
}
+namespace random {
+namespace detail {
+/**
+ * The ranlux family of generators are described in
+ *
+ * @blockquote
+ * "A portable high-quality random number generator for lattice field theory
+ * calculations", M. Luescher, Computer Physics Communications, 79 (1994)
+ * pp 100-110.
+ * @endblockquote
+ *
+ * The levels are given in
+ *
+ * @blockquote
+ * "RANLUX: A Fortran implementation ofthe high-quality
+ * pseudorandom number generator of Luescher", F. James,
+ * Computer Physics Communications 79 (1994) 111-114
+ * @endblockquote
+ */
+class ranlux_documentation {};
+}
+}
+
+/** @copydoc boost::random::detail::ranlux_documentation */
typedef random::discard_block<random::ranlux_base, 223, 24> ranlux3;
+/** @copydoc boost::random::detail::ranlux_documentation */
typedef random::discard_block<random::ranlux_base, 389, 24> ranlux4;
+/** @copydoc boost::random::detail::ranlux_documentation */
typedef random::discard_block<random::ranlux_base_01, 223, 24> ranlux3_01;
+/** @copydoc boost::random::detail::ranlux_documentation */
typedef random::discard_block<random::ranlux_base_01, 389, 24> ranlux4_01;
+/** @copydoc boost::random::detail::ranlux_documentation */
typedef random::discard_block<random::ranlux64_base_01, 223, 24> ranlux64_3_01;
+/** @copydoc boost::random::detail::ranlux_documentation */
typedef random::discard_block<random::ranlux64_base_01, 389, 24> ranlux64_4_01;
#if !defined(BOOST_NO_INT64_T) && !defined(BOOST_NO_INTEGRAL_INT64_T)
namespace random {
typedef random::subtract_with_carry<int64_t, (int64_t(1)<<48), 10, 24, 0> ranlux64_base;
}
+/** @copydoc boost::random::detail::ranlux_documentation */
typedef random::discard_block<random::ranlux64_base, 223, 24> ranlux64_3;
+/** @copydoc boost::random::detail::ranlux_documentation */
typedef random::discard_block<random::ranlux64_base, 389, 24> ranlux64_4;
#endif /* !BOOST_NO_INT64_T && !BOOST_NO_INTEGRAL_INT64_T */
Modified: trunk/boost/random/shuffle_output.hpp
==============================================================================
--- trunk/boost/random/shuffle_output.hpp (original)
+++ trunk/boost/random/shuffle_output.hpp 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -28,7 +28,30 @@
namespace boost {
namespace random {
-// Carter Bays and S.D. Durham 1979
+/**
+ * Instatiations of class template shuffle_output model a
+ * \pseudo_random_number_generator. It mixes the output
+ * of some (usually \linear_congruential) \uniform_random_number_generator
+ * to get better statistical properties.
+ * The algorithm is described in
+ *
+ * @blockquote
+ * "Improving a poor random number generator", Carter Bays
+ * and S.D. Durham, ACM Transactions on Mathematical Software,
+ * Vol 2, No. 1, March 1976, pp. 59-64.
+ * http://doi.acm.org/10.1145/355666.355670
+ * @endblockquote
+ *
+ * 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.
+ *
+ * Template parameters are the base generator and the array
+ * length k, which should be around 100. The template parameter
+ * val is the validation value checked by validation.
+ */
template<class UniformRandomNumberGenerator, int k,
#ifndef BOOST_NO_DEPENDENT_TYPES_IN_TEMPLATE_VALUE_PARAMETERS
typename UniformRandomNumberGenerator::result_type
@@ -45,18 +68,45 @@
BOOST_STATIC_CONSTANT(bool, has_fixed_range = false);
BOOST_STATIC_CONSTANT(int, buffer_size = k);
+ /**
+ * Constructs a @c shuffle_output generator by invoking the
+ * default constructor of the base generator.
+ *
+ * Complexity: Exactly k+1 invocations of the base generator.
+ */
shuffle_output() : _rng() { init(); }
#if defined(BOOST_MSVC) && _MSC_VER < 1300
// MSVC does not implicitly generate the copy constructor here
shuffle_output(const shuffle_output & x)
: _rng(x._rng), y(x.y) { std::copy(x.v, x.v+k, v); }
#endif
+ /**
+ * Constructs a shuffle_output generator by invoking the one-argument
+ * constructor of the base generator with the parameter seed.
+ *
+ * Complexity: Exactly k+1 invocations of the base generator.
+ */
template<class T>
explicit shuffle_output(T s) : _rng(s) { init(); }
+ /**
+ * Constructs a shuffle_output generator by using a copy
+ * of the provided generator.
+ *
+ * Precondition: The template argument UniformRandomNumberGenerator
+ * shall denote a CopyConstructible type.
+ *
+ * Complexity: Exactly k+1 invocations of the base generator.
+ */
explicit shuffle_output(const base_type & rng) : _rng(rng) { init(); }
template<class It> shuffle_output(It& first, It last)
: _rng(first, last) { init(); }
void seed() { _rng.seed(); init(); }
+ /**
+ * Invokes the one-argument seed method of the base generator
+ * with the parameter seed and re-initializes the internal buffer array.
+ *
+ * Complexity: Exactly k+1 invocations of the base generator.
+ */
template<class T>
void seed(T s) { _rng.seed(s); init(); }
template<class It> void seed(It& first, It last)
@@ -165,6 +215,15 @@
} // namespace random
// validation by experiment from Harry Erwin's generator.h (private e-mail)
+/**
+ * According to Harry Erwin (private e-mail), the specialization
+ * @c kreutzer1986 was suggested in:
+ *
+ * @blockquote
+ * "System Simulation: Programming Styles and Languages (International
+ * Computer Science Series)", Wolfgang Kreutzer, Addison-Wesley, December 1986.
+ * @endblockquote
+ */
typedef random::shuffle_output<
random::linear_congruential<uint32_t, 1366, 150889, 714025, 0>,
97, 139726> kreutzer1986;
Modified: trunk/boost/random/subtract_with_carry.hpp
==============================================================================
--- trunk/boost/random/subtract_with_carry.hpp (original)
+++ trunk/boost/random/subtract_with_carry.hpp 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -62,10 +62,19 @@
carry = value / modulus;
}
}
-# endif
-// subtract-with-carry generator
-// Marsaglia and Zaman
+# endif
+/**
+ * Instantiations of @c subtract_with_carry model a
+ * \pseudo_random_number_generator. The algorithm is
+ * described in
+ *
+ * @blockquote
+ * "A New Class of Random Number Generators", George
+ * Marsaglia and Arif Zaman, Annals of Applied Probability,
+ * Volume 1, Number 3 (1991), 462-480.
+ * @endblockquote
+ */
template<class IntType, IntType m, unsigned int s, unsigned int r,
IntType val>
class subtract_with_carry
@@ -205,11 +214,13 @@
#endif
private:
+ /// \cond hide_private_members
// returns x(i-r+index), where index is in 0..r-1
IntType compute(unsigned int index) const
{
return x[(k+index) % long_lag];
}
+ /// \endcond
// state representation; next output (state) is x(i)
// x[0] ... x[k] x[k+1] ... x[long_lag-1] represents
@@ -248,6 +259,7 @@
// use a floating-point representation to produce values in [0..1)
+/** @copydoc boost::random::subtract_with_carry */
template<class RealType, int w, unsigned int s, unsigned int r, int val=0>
class subtract_with_carry_01
{
@@ -269,6 +281,7 @@
{ init_modulus(); seed(first,last); }
private:
+ /// \cond hide_private_members
void init_modulus()
{
#ifndef BOOST_NO_STDC_NAMESPACE
@@ -277,6 +290,7 @@
#endif
_modulus = pow(RealType(2), word_size);
}
+ /// \endcond hide_private_members
public:
// compiler-generated copy ctor and assignment operator are fine
@@ -416,7 +430,9 @@
#endif
private:
+ /// \cond hide_private_members
RealType compute(unsigned int index) const;
+ /// \endcond
unsigned int k;
RealType carry;
RealType x[long_lag];
@@ -435,12 +451,13 @@
const unsigned int subtract_with_carry_01<RealType, w, s, r, val>::short_lag;
#endif
+/// \cond hide_private_members
template<class RealType, int w, unsigned int s, unsigned int r, int val>
RealType subtract_with_carry_01<RealType, w, s, r, val>::compute(unsigned int index) const
{
return x[(k+index) % long_lag];
}
-
+/// \endcond
} // namespace random
} // namespace boost
Modified: trunk/boost/random/triangle_distribution.hpp
==============================================================================
--- trunk/boost/random/triangle_distribution.hpp (original)
+++ trunk/boost/random/triangle_distribution.hpp 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -23,8 +23,12 @@
namespace boost {
-// triangle distribution, with a smallest, b most probable, and c largest
-// value.
+/**
+ * Instantiations of @c triangle_distribution model a \random_distribution.
+ * A @c triangle_distribution has three parameters, @c a, @c b, and @c c,
+ * which are the smallest, the most probable and the largest values of
+ * the distribution respectively.
+ */
template<class RealType = double>
class triangle_distribution
{
@@ -32,6 +36,12 @@
typedef RealType input_type;
typedef RealType result_type;
+ /**
+ * Constructs a @c triangle_distribution with the parameters
+ * @c a, @c b, and @c c.
+ *
+ * Preconditions: a <= b <= c.
+ */
explicit triangle_distribution(result_type a_arg = result_type(0),
result_type b_arg = result_type(0.5),
result_type c_arg = result_type(1))
@@ -42,8 +52,12 @@
}
// compiler-generated copy ctor and assignment operator are fine
+
+ /** Returns the @c a parameter of the distribution */
result_type a() const { return _a; }
+ /** Returns the @c b parameter of the distribution */
result_type b() const { return _b; }
+ /** Returns the @c c parameter of the distribution */
result_type c() const { return _c; }
void reset() { }
@@ -81,6 +95,7 @@
#endif
private:
+ /// \cond hide_private_members
void init()
{
#ifndef BOOST_NO_STDC_NAMESPACE
@@ -92,6 +107,7 @@
q1 = d1 / d2;
p1 = sqrt(d1 * d2);
}
+ /// \endcond
result_type _a, _b, _c;
result_type d1, d2, d3, q1, p1;
Modified: trunk/boost/random/uniform_01.hpp
==============================================================================
--- trunk/boost/random/uniform_01.hpp (original)
+++ trunk/boost/random/uniform_01.hpp 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -27,6 +27,53 @@
namespace boost {
+#ifdef BOOST_RANDOM_DOXYGEN
+
+/**
+ * The distribution function uniform_01 models a \random_distribution.
+ * On each invocation, it returns a random floating-point value
+ * uniformly distributed in the range [0..1).
+ *
+ * The template parameter RealType shall denote a float-like value type
+ * with support for binary operators +, -, and /.
+ *
+ * Note: 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) @c boost::bigfloat class with random bits efficiently.
+ * It's probably time for a traits class.
+ */
+template<class RealType = double>
+class uniform_01
+{
+public:
+ typedef RealType input_type;
+ typedef RealType result_type;
+ result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const;
+ result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const;
+ void reset();
+
+ template<class Engine>
+ result_type operator()(Engine& eng);
+
+#ifndef BOOST_RANDOM_NO_STREAM_OPERATORS
+ template<class CharT, class Traits>
+ friend std::basic_ostream<CharT,Traits>&
+ operator<<(std::basic_ostream<CharT,Traits>& os, const new_uniform_01&)
+ {
+ return os;
+ }
+
+ template<class CharT, class Traits>
+ friend std::basic_istream<CharT,Traits>&
+ operator>>(std::basic_istream<CharT,Traits>& is, new_uniform_01&)
+ {
+ return is;
+ }
+#endif
+};
+
+#else
+
namespace detail {
template<class RealType>
@@ -217,6 +264,8 @@
#endif
};
+#endif
+
} // namespace boost
#include <boost/random/detail/enable_warnings.hpp>
Modified: trunk/boost/random/uniform_int.hpp
==============================================================================
--- trunk/boost/random/uniform_int.hpp (original)
+++ trunk/boost/random/uniform_int.hpp 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -29,15 +29,30 @@
namespace boost {
-// uniform integer distribution on [min, max]
+/**
+ * The distribution function uniform_int 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}.
+ *
+ * The template parameter IntType shall denote an integer-like value type.
+ */
template<class IntType = int>
class uniform_int
{
public:
typedef IntType input_type;
typedef IntType result_type;
+
+ /// \cond hide_private_members
typedef typename make_unsigned<result_type>::type range_type;
+ /// \endcond
+ /**
+ * Constructs a uniform_int object. @c min and @c max are
+ * the parameters of the distribution.
+ *
+ * Requires: min <= max
+ */
explicit uniform_int(IntType min_arg = 0, IntType max_arg = 9)
: _min(min_arg), _max(max_arg)
{
@@ -49,7 +64,13 @@
init();
}
+ /**
+ * Returns: The "min" parameter of the distribution
+ */
result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return _min; }
+ /**
+ * Returns: The "max" parameter of the distribution
+ */
result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return _max; }
void reset() { }
@@ -93,6 +114,8 @@
#endif
private:
+
+ /// \cond hide_private_members
template<class Engine>
static result_type generate(Engine& eng, result_type min_value, result_type /*max_value*/, range_type range)
{
@@ -253,6 +276,8 @@
_range = random::detail::subtract<result_type>()(_max, _min);
}
+ /// \endcond
+
// The result_type may be signed or unsigned, but the _range is always
// unsigned.
result_type _min, _max;
Modified: trunk/boost/random/uniform_on_sphere.hpp
==============================================================================
--- trunk/boost/random/uniform_on_sphere.hpp (original)
+++ trunk/boost/random/uniform_on_sphere.hpp 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -24,6 +24,16 @@
namespace boost {
+/**
+ * Instantiations of class template uniform_on_sphere model a
+ * \random_distribution. Such a distribution produces random
+ * numbers uniformly distributed on the unit sphere of arbitrary
+ * dimension @c dim. The @c Cont template parameter must be a STL-like
+ * container type with begin and end operations returning non-const
+ * ForwardIterators of type @c Cont::iterator. Each invocation of the
+ * @c UniformRandomNumberGenerator shall result in a floating-point
+ * value in the range [0,1).
+ */
template<class RealType = double, class Cont = std::vector<RealType> >
class uniform_on_sphere
{
@@ -31,6 +41,10 @@
typedef RealType input_type;
typedef Cont result_type;
+ /**
+ * Constructs a @c uniform_on_sphere distribution.
+ * @c dim is the dimension of the sphere.
+ */
explicit uniform_on_sphere(int dim = 2) : _container(dim), _dim(dim) { }
// compiler-generated copy ctor and assignment operator are fine
Modified: trunk/boost/random/uniform_real.hpp
==============================================================================
--- trunk/boost/random/uniform_real.hpp (original)
+++ trunk/boost/random/uniform_real.hpp 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -26,7 +26,17 @@
namespace boost {
-// uniform distribution on a real range
+/**
+ * The distribution function uniform_real models a random distribution.
+ * On each invocation, it returns a random floating-point value uniformly
+ * distributed in the range [min..max). The value is computed using
+ * std::numeric_limits<RealType>::digits random binary digits, i.e.
+ * the mantissa of the floating-point value is completely filled with
+ * random bits.
+ *
+ * Note: The current implementation is buggy, because it may not fill
+ * all of the mantissa with random bits.
+ */
template<class RealType = double>
class uniform_real
{
@@ -34,6 +44,12 @@
typedef RealType input_type;
typedef RealType result_type;
+ /**
+ * Constructs a uniform_real object. @c min and @c max are the
+ * parameters of the distribution.
+ *
+ * Requires: min <= max
+ */
explicit uniform_real(RealType min_arg = RealType(0),
RealType max_arg = RealType(1))
: _min(min_arg), _max(max_arg)
@@ -46,7 +62,13 @@
// compiler-generated copy ctor and assignment operator are fine
+ /**
+ * Returns: The "min" parameter of the distribution
+ */
result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return _min; }
+ /**
+ * Returns: The "max" parameter of the distribution
+ */
result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return _max; }
void reset() { }
Modified: trunk/boost/random/uniform_smallint.hpp
==============================================================================
--- trunk/boost/random/uniform_smallint.hpp (original)
+++ trunk/boost/random/uniform_smallint.hpp 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -30,6 +30,52 @@
// uniform integer distribution on a small range [min, max]
+/**
+ * The distribution function uniform_smallint 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.
+ *
+ * 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 @c uniform_smallint. 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>).
+ *
+ * The template parameter IntType shall denote an integer-like value type.
+ *
+ * Note: 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.
+ *
+ * Note: 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>.
+ */
template<class IntType = int>
class uniform_smallint
{
@@ -37,6 +83,10 @@
typedef IntType input_type;
typedef IntType result_type;
+ /**
+ * Constructs a @c uniform_smallint. @c min and @c max are the
+ * lower and upper bounds of the output range, respectively.
+ */
explicit uniform_smallint(IntType min_arg = 0, IntType max_arg = 9)
: _min(min_arg), _max(max_arg)
{
Modified: trunk/boost/random/variate_generator.hpp
==============================================================================
--- trunk/boost/random/variate_generator.hpp (original)
+++ trunk/boost/random/variate_generator.hpp 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -33,6 +33,8 @@
namespace boost {
+/// \cond hide_private_members
+
namespace random {
namespace detail {
@@ -83,7 +85,31 @@
} // namespace detail
} // namespace random
+///\endcond
+/**
+ * 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.
+ *
+ * Instantations of class template @c variate_generator model
+ * a \number_generator.
+ *
+ * The argument for the template parameter Engine shall be of
+ * the form U, U&, or U*, where U models a
+ * \uniform_random_number_generator. Then, the member
+ * engine_value_type names U (not the pointer or reference to U).
+ *
+ * Specializations of @c variate_generator satisfy the
+ * requirements of CopyConstructible. They also satisfy the
+ * requirements of Assignable unless the template parameter
+ * Engine is of the form U&.
+ *
+ * The complexity of all functions specified in this section
+ * is constant. No function described in this section except
+ * the constructor throws an exception.
+ */
template<class Engine, class Distribution>
class variate_generator
{
@@ -96,20 +122,77 @@
typedef Distribution distribution_type;
typedef typename Distribution::result_type result_type;
+ /**
+ * Constructs a @c variate_generator object with the associated
+ * \uniform_random_number_generator eng and the associated
+ * \random_distribution d.
+ *
+ * Throws: If and what the copy constructor of Engine or
+ * Distribution throws.
+ */
variate_generator(Engine e, Distribution d)
: _eng(decorated_engine(e)), _dist(d) { }
+ /**
+ * Returns: distribution()(e)
+ *
+ * Notes: The sequence of numbers produced by the
+ * \uniform_random_number_generator e, s<sub>e</sub>, is
+ * obtained from the sequence of numbers produced by the
+ * associated \uniform_random_number_generator eng, s<sub>eng</sub>,
+ * as follows: Consider the values of @c numeric_limits<T>::is_integer
+ * for @c T both @c Distribution::input_type and
+ * @c engine_value_type::result_type. If the values for both types are
+ * true, then se is identical to s<sub>eng</sub>. Otherwise, if the
+ * values for both types are false, then the numbers in s<sub>eng</sub>
+ * are divided by engine().max()-engine().min() to obtain the numbers
+ * in s<sub>e</sub>. Otherwise, if the value for
+ * @c engine_value_type::result_type is true and the value for
+ * @c Distribution::input_type is false, then the numbers in s<sub>eng</sub>
+ * are divided by engine().max()-engine().min()+1 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 @c engine_value_type::result_type to
+ * @c Distribution::input_type is performed. If such a conversion does
+ * not exist, the program is ill-formed.
+ */
result_type operator()() { return _dist(_eng); }
+ /**
+ * Returns: distribution()(e, value).
+ * For the semantics of e, see the description of operator()().
+ */
template<class T>
result_type operator()(T value) { return _dist(_eng, value); }
+ /**
+ * Returns: A reference to the associated uniform random number generator.
+ */
engine_value_type& engine() { return _eng.base().base(); }
+ /**
+ * Returns: A reference to the associated uniform random number generator.
+ */
const engine_value_type& engine() const { return _eng.base().base(); }
+ /**
+ * Returns: A reference to the associated random distribution.
+ */
distribution_type& distribution() { return _dist; }
+ /**
+ * Returns: A reference to the associated random distribution.
+ */
const distribution_type& distribution() const { return _dist; }
+ /**
+ * Precondition: distribution().min() is well-formed
+ *
+ * Returns: distribution().min()
+ */
result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return (distribution().min)(); }
+ /**
+ * Precondition: distribution().max() is well-formed
+ *
+ * Returns: distribution().max()
+ */
result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return (distribution().max)(); }
private:
Modified: trunk/boost/random/xor_combine.hpp
==============================================================================
--- trunk/boost/random/xor_combine.hpp (original)
+++ trunk/boost/random/xor_combine.hpp 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -27,13 +27,24 @@
namespace boost {
namespace random {
+/// \cond hide_private_members
#ifndef BOOST_NO_DEPENDENT_TYPES_IN_TEMPLATE_VALUE_PARAMETERS
#define BOOST_RANDOM_VAL_TYPE typename URNG1::result_type
#else
#define BOOST_RANDOM_VAL_TYPE uint32_t
#endif
+/// \endcond
-template<class URNG1, int s1, class URNG2, int s2, BOOST_RANDOM_VAL_TYPE val = 0>
+/**
+ * Instantiations of @c xor_combine model a \pseudo_random_number_generator.
+ * To produce its output it invokes each of the base generators, shifts
+ * their results and xors them together.
+ */
+template<class URNG1, int s1, class URNG2, int s2
+#ifndef BOOST_RANDOM_DOXYGEN
+, BOOST_RANDOM_VAL_TYPE val = 0
+#endif
+>
class xor_combine
{
public:
@@ -45,25 +56,58 @@
BOOST_STATIC_CONSTANT(int, shift1 = s1);
BOOST_STATIC_CONSTANT(int, shift2 = s2);
+ /**
+ * Constructors a @c xor_combine by default constructing
+ * both base generators.
+ */
xor_combine() : _rng1(), _rng2()
{ }
+ /**
+ * Constructs a @c xor_combine by copying two base generators.
+ */
xor_combine(const base1_type & rng1, const base2_type & rng2)
: _rng1(rng1), _rng2(rng2) { }
+ /**
+ * Constructs a @c xor_combine, seeding both base generators
+ * with @c v.
+ */
xor_combine(const result_type & v)
: _rng1(v), _rng2(v) { }
+ /**
+ * Constructs a @c xor_combine, seeding both base generators
+ * with values from the iterator range [first, last) and changes
+ * first to point to the element after the last one used. If there
+ * are not enough elements in the range to seed both generators,
+ * throws @c std::invalid_argument.
+ */
template<class It> xor_combine(It& first, It last)
: _rng1(first, last), _rng2( /* advanced by other call */ first, last) { }
+ /**
+ * Calls @c seed() for both base generators.
+ */
void seed() { _rng1.seed(); _rng2.seed(); }
+ /**
+ * @c seeds both base generators with @c v.
+ */
void seed(const result_type & v) { _rng1.seed(v); _rng2.seed(v); }
+ /**
+ * seeds both base generators with values from the iterator
+ * range [first, last) and changes first to point to the element
+ * after the last one used. If there are not enough elements in
+ * the range to seed both generators, throws @c std::invalid_argument.
+ */
template<class It> void seed(It& first, It last)
{
_rng1.seed(first, last);
_rng2.seed(first, last);
}
+ /** Returns the first base generator. */
const base1_type& base1() { return _rng1; }
+ /** Returns the second base generator. */
const base2_type& base2() { return _rng2; }
+ /** Returns the next value of the generator. */
result_type operator()()
{
// MSVC fails BOOST_STATIC_ASSERT with std::numeric_limits at class scope
@@ -75,7 +119,13 @@
return (_rng1() << s1) ^ (_rng2() << s2);
}
+ /**
+ * Returns the smallest value that the generator can produce.
+ */
result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return std::min BOOST_PREVENT_MACRO_SUBSTITUTION((_rng1.min)(), (_rng2.min)()); }
+ /**
+ * Returns the largest value that the generator can produce.
+ */
result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return std::max BOOST_PREVENT_MACRO_SUBSTITUTION((_rng1.min)(), (_rng2.max)()); }
static bool validation(result_type x) { return val == x; }
Added: trunk/libs/random/doc/Jamfile.v2
==============================================================================
--- (empty file)
+++ trunk/libs/random/doc/Jamfile.v2 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -0,0 +1,113 @@
+# Jamfile.v2
+#
+# Copyright (c) 2009
+# Steven Watanabe
+#
+# Distributed under the Boost Sofware License, Version 1.0. (See
+# accompanying file LICENSE_1_0.txt or copy at
+# http://www.boost.org/LICENSE_1_0.txt)
+
+using quickbook ;
+using doxygen ;
+import boostbook ;
+import regex ;
+import os ;
+
+doxygen_files =
+ additive_combine
+ bernoulli_distribution
+ binomial_distribution
+ cauchy_distribution
+ discard_block
+ exponential_distribution
+ gamma_distribution
+ geometric_distribution
+ inversive_congruential
+ lagged_fibonacci
+ linear_congruential
+ linear_feedback_shift
+ lognormal_distribution
+ mersenne_twister
+ normal_distribution
+ poisson_distribution
+ random_number_generator
+ ranlux
+ shuffle_output
+ subtract_with_carry
+ triangle_distribution
+ uniform_01
+ uniform_int
+ uniform_on_sphere
+ uniform_real
+ uniform_smallint
+ variate_generator
+ xor_combine
+;
+
+# temporary hack for local docs
+local BOOST_ROOT = ../../../.. ;
+
+doxygen reference :
+ ../../../boost/random/$(doxygen_files).hpp
+ ../../../boost/nondet_random.hpp
+ ../../../boost/random.hpp
+ :
+ <doxygen:param>EXPAND_ONLY_PREDEF=YES
+ <doxygen:param>"ALIASES= \\
+ xmlnote=\"@xmlonly <note><para> @endxmlonly\" \\
+ 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\" \\
+ nondeterministic_random_number_generator=\"@xmlonly <link linkend=\\\"boost_random.reference.concepts.non_deterministic_uniform_random_number_generator\\\">non-deterministic random number generator</link> @endxmlonly\" \\
+ number_generator=\"@xmlonly <link linkend=\\\"boost_random.reference.concepts.number_generator\\\">number generator</link> @endxmlonly\" \\
+ generators=\"@xmlonly <link linkend=\\\"boost_random.reference.generators\\\">generators</link> @endxmlonly\" \\
+ distributions=\"@xmlonly <link linkend=\\\"boost_random.reference.distributions\\\">distributions</link> @endxmlonly\" \\
+ additive_combine=\"@xmlonly <classname alt=\\\"boost::random::additive_combine\\\">additive_combine</classname> @endxmlonly\" \\
+ discard_block=\"@xmlonly <classname alt=\\\"boost::random::discard_block\\\">discard_block</classname> @endxmlonly\" \\
+ lagged_fibonacci=\"@xmlonly<classname alt=\\\"boost::random::lagged_fibonacci\\\">lagged_fibonacci</classname>@endxmlonly\" \\
+ linear_congruential=\"@xmlonly<classname alt=\\\"boost::random::linear_congruential\\\">linear_congruential</classname>@endxmlonly\" \\
+ minstd_rand=\"@xmlonly <classname alt=\\\"boost::minstd_rand\\\">minstd_rand</classname> @endxmlonly\" \\
+ minstd_rand0=\"@xmlonly <classname alt=\\\"boost::minstd_rand0\\\">minstd_rand0</classname> @endxmlonly\" \\
+ rand48=\"@xmlonly <classname alt=\\\"boost::rand48\\\">rand48</classname> @endxmlonly\" \\
+ mt11213b=\"@xmlonly <classname alt=\\\"boost::mt11213b\\\">mt11213b</classname> @endxmlonly\" \\
+ mt19937=\"@xmlonly <classname alt=\\\"boost::mt19937\\\">mt19937</classname> @endxmlonly\" \\
+ ecuyer1988=\"@xmlonly <classname alt=\\\"boost::ecuyer1988\\\">ecuyer1988</classname> @endxmlonly\" \\
+ lagged_fibonacci607=\"@xmlonly <classname alt=\\\"boost::lagged_fibonacci607\\\">lagged_fibonacci607</classname> @endxmlonly\" \\
+ lagged_fibonacci44497=\"@xmlonly <classname alt=\\\"boost::lagged_fibonacci44497\\\">lagged_fibonacci44497</classname> @endxmlonly\" \\
+ bernoulli_distribution=\"@xmlonly <classname alt=\\\"boost::bernoulli_distribution\\\">bernoulli_distribution</classname> @endxmlonly\" \\
+ cauchy_distribution=\"@xmlonly <classname alt=\\\"boost::cauchy_distribution\\\">cauchy_distribution</classname> @endxmlonly\" \\
+ uniform_01=\"@xmlonly<classname alt=\\\"boost::uniform_01\\\">uniform_01</classname>@endxmlonly\" \\
+ random_device=\"@xmlonly<classname alt=\\\"boost::random_device\\\">random_device</classname>@endxmlonly\""
+ <doxygen:param>HIDE_UNDOC_MEMBERS=NO
+ <doxygen:param>QUIET=YES
+ <doxygen:param>WARN_IF_UNDOCUMENTED=NO
+ <doxygen:param>EXTRACT_PRIVATE=NO
+ <doxygen:param>ENABLE_PREPROCESSING=YES
+ <doxygen:param>MACRO_EXPANSION=YES
+ <doxygen:param>SEARCH_INCLUDES=NO
+ <doxygen:param>"PREDEFINED= \\
+ \"BOOST_RANDOM_DOXYGEN=1\" \\
+ \"BOOST_PREVENT_MACRO_SUBSTITUTION=\" \\
+ \"BOOST_STATIC_ASSERT(x)=\" \\
+ \"BOOST_STATIC_CONSTANT(type,value)=static const type value\" \\
+ \"BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(Self,T,t)=explicit Self(T t)\" \\
+ \"BOOST_RANDOM_DETAIL_GENERATOR_CONSTRUCTOR(Self,T,t)=template<class T> explicit Self(T& t)\" \\
+ \"BOOST_RANDOM_DETAIL_ARITHMETIC_SEED(Self,T,t)=void seed(T t)\" \\
+ \"BOOST_RANDOM_DETAIL_GENERATOR_SEED(Self,T,t)=template<class T> void seed(T& t)\""
+ <reftitle>"Headers"
+ <doxygen:xml-imagedir>images/random
+;
+
+xml random : random.qbk ;
+
+boostbook standalone :
+ random
+ :
+ <implicit-dependency>reference
+ <xsl:param>boost.root=../../../..
+ <xsl:param>chunk.section.depth=2
+;
Added: trunk/libs/random/doc/concepts.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/random/doc/concepts.qbk 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -0,0 +1,274 @@
+[section Introduction]
+
+Random numbers are required in a number of different problem domains, such as
+
+* numerics (simulation, Monte-Carlo integration)
+* games (non-deterministic enemy behavior)
+* security (key generation)
+* testing (random coverage in white-box tests)
+
+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
+
+[:"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]
+
+Depending on the requirements of the problem domain, different variations of
+random number generators are appropriate:
+
+* non-deterministic random number generator
+* pseudo-random number generator
+* quasi-random number generator
+
+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.
+
+The goals for this library are the following:
+
+* allow easy integration of third-party random-number generators
+* define a validation interface for the generators
+* provide easy-to-use front-end classes which model popular distributions
+* provide maximum efficiency
+* allow control on quantization effects in front-end processing (not yet done)
+
+[endsect]
+
+[section Number Generator]
+
+A number generator is a /function object/ (std:20.3 [lib.function.objects]) that
+takes zero arguments. Each call to `operator()` returns a number. In the
+following table, X denotes a number generator class returning objects of type
+T, and u is a value of X.
+
+[table NumberGenerator requirements
+ [[expression] [return type] [pre/post-condition]]
+ [[`X::result_type`] [`T`] [`std::numeric_limits<T>::is_specialized` is
+ `true`, `T` is __LessThanComparable]]
+ [[`u.operator()()`] [`T`] [-]]
+]
+
+[note The NumberGenerator requirements do not impose any restrictions on the
+characteristics of the returned numbers.]
+
+[endsect]
+
+[section Uniform Random Number Generator]
+
+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.
+
+The /tight lower bound/ of some (finite) set S is the (unique) member l in S, so
+that for all v in S, l <= v holds. Likewise, the /tight upper bound/ of some
+(finite) set S is the (unique) member u in S, so that for all v in S, v <= u
+holds.
+
+In the following table, X denotes a number generator class returning objects
+of type T, and v is a const value of X.
+
+[table UniformRandomNumberGenerator requirements
+ [[expression] [return type] [pre/post-condition]]
+ [[`X::has_fixed_range`] [`bool`] [compile-time constant; if `true`, the range
+ on which the random numbers are uniformly
+ distributed is known at compile-time and
+ members `min_value` and `max_value` exist.
+ Note: This flag may also be `false` due to
+ compiler limitations]]
+ [[`X::min_value`] [`T`] [compile-time constant; `min_value` is only defined if
+ `has_fixed_range` is `true`. If it exists, it is
+ equal to `v.min()`.]]
+ [[`X::max_value`] [`T`] [compile-time constant; `max_value` is only defined if
+ `has_fixed_range` is `true`. If it exists, it is
+ equal to `v.max()`]]
+ [[`v.min()`] [`T`] [tight lower bound on the set of all values returned by
+ `operator()`. The return value of this function shall not
+ change during the lifetime of the object.]]
+ [[`v.max()`] [`T`] [if `std::numeric_limits<T>::is_integer`, tight upper
+ bound on the set of all values returned by `operator()`,
+ otherwise, the smallest representable number larger than
+ the tight upper bound on the set of all values returned
+ by `operator()`. In any case, the return value of this
+ function shall not change during the lifetime of the
+ object.]]
+]
+
+The member functions `min`, `max`, and `operator()` shall have amortized
+constant time complexity.
+
+[note For integer generators (i.e. integer `T`), the generated values `x`
+fulfill `min() <= x <= max()`, for non-integer generators (i.e. non-integer
+`T`), the generated values `x` fulfill `min() <= x < max()`.
+
+Rationale: The range description with min and max 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.
+
+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.]
+
+[note The __UniformRandomNumberGenerator concept does not require
+`operator()(long)` and thus it does not fulfill the `RandomNumberGenerator`
+(std:25.2.11 \[lib.alg.random.shuffle\]) requirements. Use the
+__random_number_generator adapter for that.
+
+Rationale: `operator()(long)` is not provided, because mapping the output of
+some generator with integer range to a different integer range is not trivial.]
+
+[endsect]
+
+[section Non-deterministic Uniform Random Number Generator]
+
+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.
+
+The class __random_device is a model for a non-deterministic random number
+generator.
+
+[note This type of random-number generator is useful for security
+applications, where it is important to prevent an outside attacker from
+guessing the numbers and thus obtaining 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.]
+
+[endsect]
+
+[section Pseudo-Random Number Generator]
+
+A pseudo-random number generator is a __UniformRandomNumberGenerator which
+provides a deterministic sequence of pseudo-random numbers, based on some
+algorithm and internal state. [classref boost::random::linear_congruential
+Linear congruential] and [classref boost::random::inversive_congruential
+inversive congruential] generators are examples of such [prng 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.
+
+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.
+
+[note Because the state of a pseudo-random number generator is necessarily
+finite, the sequence of numbers returned by the generator will loop
+eventually.]
+
+In addition to the __UniformRandomNumberGenerator requirements,
+a pseudo-random number generator has some additional requirements. In the
+following table, `X` denotes a pseudo-random number generator class returning
+objects of type `T`, `x` is a value of `T`, `u` is a value of `X`, and `v` is
+a const value of `X`.
+
+[table PseudoRandomNumberGenerator requirements
+ [[expression] [return type] [pre/post-condition]]
+ [[`X()`] [-] [creates a generator in some implementation-defined state.
+ Note: Several generators thusly created may possibly produce
+ dependent or identical sequences of random numbers.]]
+ [[`explicit X(...)`] [-] [creates a generator with user-provided state; the
+ implementation shall specify the constructor
+ argument(s)]]
+ [[`u.seed(...)`] [`void`] [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.]]
+ [[`X::validation(x)`] [`bool`] [compares the pre-computed and hardcoded
+ 10001th element in the generator's random
+ number sequence with x. The generator must
+ have been constructed by its default
+ constructor and seed must not have been
+ called for the validation to be
+ meaningful.]]
+]
+
+[note The seed member function is similar to the assign member function in
+STL containers. However, the naming did not seem appropriate.]
+
+Classes which model a pseudo-random number generator shall also model
+__EqualityComparable, i.e. implement `operator==`. Two pseudo-random number
+generators are defined to be /equivalent/ if they both return an identical
+sequence of numbers starting from a given state.
+
+Classes which model a pseudo-random number generator should also model the
+__Streamable concept, i.e. implement `operator<<` and `operator>>`. If so,
+`operator<<` writes all current state of the pseudo-random number generator
+to the given `ostream` so that `operator>>` can restore the state at a later
+time. The state shall be written in a platform-independent manner, but it is
+assumed that the `locales` 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.
+
+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-const) reference.
+
+The classes __rand48, __minstd_rand, and __mt19937 are models for a
+pseudo-random number generator.
+
+[note This type of random-number generator is useful for numerics, games and
+testing. The non-zero arguments constructor(s) and the `seed()` 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.]
+
+[endsect]
+
+[section Random Distribution]
+
+A random distribution produces random numbers distributed according to some
+distribution, given uniformly distributed random values as input. In the
+following table, `X` denotes a random distribution class returning objects of
+type `T`, `u` is a value of `X`, `x` is a (possibly const) value of `X`, and
+`e` is an lvalue of an arbitrary type that meets the requirements of a
+__UniformRandomNumberGenerator, returning values of type `U`.
+
+[table Random distribution requirements (in addition to NumberGenerator, CopyConstructible, and Assignable)
+ [[expression] [return type] [pre/post-condition] [complexity]]
+ [[`X::input_type`] [`U`] [-] [compile-time]]
+ [[`u.reset()`] [`void`] [subsequent uses of `u` do not depend on values
+ produced by `e` prior to invoking `reset`.]
+ [constant]]
+ [[`u(e)`] [`T`] [the sequence of numbers returned by successive invocations
+ with the same object `e` is randomly distributed with some
+ probability density function `p(x)`]
+ [amortized constant number of invocations of `e`]]
+ [[`os << x`] [`std::ostream&`] [writes a textual representation for the
+ parameters and additional internal data of
+ the distribution `x` to `os`.
+ post: The `os.fmtflags` and fill character
+ are unchanged.]
+ [O(size of state)]]
+ [[`is >> u`] [`std::istream&`] [restores the parameters and additional
+ internal data of the distribution `u`.
+ pre: `is` provides a textual representation
+ that was previously written by `operator<<`
+ post: The `is.fmtflags` are unchanged.]
+ [O(size of state)]]
+]
+
+Additional requirements: The sequence of numbers produced by repeated
+invocations of `x(e)` does not change whether or not `os << x` is invoked
+between any of the invocations `x(e)`. If a textual representation is written
+using `os << x` and that representation is restored into the same or a
+different object `y` of the same type using `is >> y`, repeated invocations
+of `y(e)` produce the same sequence of random numbers as would repeated
+invocations of `x(e)`.
+
+[endsect]
Added: trunk/libs/random/doc/distribution_performance_linux.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/random/doc/distribution_performance_linux.qbk 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -0,0 +1,15 @@
+[table Distributions (Linux)
+ [[\[M rn/sec\]][minstd_rand][kreutzer1986][mt19937][lagged_fibonacci607]]
+ [[uniform_int][31.25][30.581][11.5607][16.0514]]
+ [[geometric][5.20833][6.66223][6.68449][6.73854]]
+ [[binomial][5.01505][21.7865][4.38982][10.9529]]
+ [[poisson][22.8311][22.1729][20.8768][24.3902]]
+ [[uniform_real][18.2815][84.0336][67.1141][72.4638]]
+ [[triangle][13.2802][33.4448][33.67][36.4964]]
+ [[exponential][6.19195][8.49618][8.2713][8.65052]]
+ [[normal polar][5.78369][6.56599][6.49773][6.48508]]
+ [[lognormal][4.13565][4.53515][4.51467][4.57875]]
+ [[cauchy][6.07533][7.92393][7.77605][8.35422]]
+ [[gamma][6.07533][7.92393][7.83085][8.34725]]
+ [[uniform_on_sphere][1.43472][1.62075][1.5625][1.5949]]
+]
Added: trunk/libs/random/doc/distribution_performance_windows.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/random/doc/distribution_performance_windows.qbk 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -0,0 +1,15 @@
+[table Distributions (Windows)
+ [[\[M rn/sec\]][minstd_rand][kreutzer1986][mt19937][lagged_fibonacci607]]
+ [[uniform_int][14.7449][27.465][6.65292][28.5714]]
+ [[geometric][7.10328][5.53649][3.73622][9.38438]]
+ [[binomial][6.20155][5.78135][2.65118][4.65463]]
+ [[poisson][15.9617][8.77886][12.5486][17.9276]]
+ [[uniform_real][49.6032][27.1223][31.6857][60.35]]
+ [[triangle][21.3356][11.7][14.2857][22.3015]]
+ [[exponential][14.3493][6.05473][10.8472][12.982]]
+ [[normal polar][4.24394][2.75748][7.04871][6.09533]]
+ [[lognormal][3.30066][1.34822][5.36913][4.0024]]
+ [[cauchy][11.4286][2.92372][12.0525][7.55629]]
+ [[gamma][10.5263][3.72523][12.1433][5.87682]]
+ [[uniform_on_sphere][0.680874][0.38004][1.18737][0.486334]]
+]
Added: trunk/libs/random/doc/distributions.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/random/doc/distributions.qbk 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -0,0 +1,64 @@
+In addition to the [link boost_random.reference.generators random number generators],
+this library provides distribution functions which map one distribution
+(often a uniform distribution provided by some generator) to another.
+
+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.
+
+[table distributions
+ [[distribution] [explanation] [example]]
+ [[__uniform_smallint] [discrete uniform distribution on a small set of integers
+ (much smaller than the range of the underlying
+ generator)]
+ [drawing from an urn]]
+ [[__uniform_int] [discrete uniform distribution on a set of integers; the
+ underlying generator may be called several times to gather
+ enough randomness for the output]
+ [drawing from an urn]]
+ [[__uniform_01] [continuous uniform distribution on the range [0,1);
+ important basis for other distributions]
+ [-]]
+ [[__uniform_real] [continuous uniform distribution on some range [min, max) of
+ real numbers]
+ [for the range [0, 2pi): randomly dropping a stick and
+ measuring its angle in radians (assuming the angle is
+ uniformly distributed)]]
+ [[__bernoulli_distribution] [Bernoulli experiment: discrete boolean valued
+ distribution with configurable probability]
+ [tossing a coin (p=0.5)]]
+ [[__binomial_distribution] [counts outcomes of repeated Bernoulli
+ experiments]
+ [tossing a coin 20 times and counting how many
+ front sides are shown]]
+ [[__cauchy_distribution][cauchy distribution][-]]
+ [[__gamma_distribution][gamma distribution][-]]
+ [[__poisson_distribution][poisson distribution]
+ [counting the number of alpha particles emitted
+ by radioactive matter in a fixed period of time]]
+ [[__geometric_distribution] [measures distance between outcomes of repeated
+ Bernoulli experiments]
+ [throwing a die several times and counting the
+ number of tries until a "6" appears for the
+ first time]]
+ [[__triangle_distribution] [triangle distribution] [-]]
+ [[__exponential_distribution] [exponential distribution]
+ [measuring the inter-arrival time of alpha
+ particles emitted by radioactive matter]]
+ [[__normal_distribution] [counts outcomes of (infinitely) repeated Bernoulli
+ experiments]
+ [tossing a coin 10000 times and counting how many
+ front sides are shown]]
+ [[__lognormal_distribution] [lognormal distribution (sometimes used in
+ simulations)]
+ [measuring the job completion time of an assembly
+ line worker]]
+ [[__uniform_on_sphere] [uniform distribution on a unit sphere of arbitrary
+ dimension]
+ [choosing a random point on Earth (assumed to be a
+ sphere) where to spend the next vacations]]
+]
Added: trunk/libs/random/doc/generator_defs.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/random/doc/generator_defs.qbk 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -0,0 +1,29 @@
+[template rand48_speed[] 68%]
+[template lrand48_run_time_speed[] 12%]
+[template minstd_rand0_speed[] 32%]
+[template minstd_rand_speed[] 26%]
+[template ecuyer_combined_speed[] 11%]
+[template kreutzer1986_speed[] 46%]
+[template hellekalek1995__inversive__speed[] 2%]
+[template mt11213b_speed[] 95%]
+[template mt19937_speed[] 100%]
+[template lagged_fibonacci607_speed[] 42%]
+[template lagged_fibonacci1279_speed[] 44%]
+[template lagged_fibonacci2281_speed[] 44%]
+[template lagged_fibonacci3217_speed[] 43%]
+[template lagged_fibonacci4423_speed[] 44%]
+[template lagged_fibonacci9689_speed[] 44%]
+[template lagged_fibonacci19937_speed[] 44%]
+[template lagged_fibonacci23209_speed[] 44%]
+[template lagged_fibonacci44497_speed[] 44%]
+[template subtract_with_carry_speed[] 72%]
+[template subtract_with_carry_01_speed[] 54%]
+[template ranlux3_speed[] 6%]
+[template ranlux4_speed[] 4%]
+[template ranlux3_01_speed[] 5%]
+[template ranlux4_01_speed[] 2%]
+[template ranlux64_3_speed[] 6%]
+[template ranlux64_4_speed[] 4%]
+[template ranlux64_3_01_speed[] 4%]
+[template ranlux64_4_01_speed[] 2%]
+[template mt19937ar_c_speed[] 97%]
Added: trunk/libs/random/doc/generator_performance_linux.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/random/doc/generator_performance_linux.qbk 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -0,0 +1,34 @@
+[table Basic Generators (Linux)
+ [[generator] [M rn/sec] [time per random number \[nsec\]] [relative speed compared to fastest \[percent\]]]
+ [[rand48][312.5][3.2][100%]]
+ [[lrand48 run-time][303.03][3.3][96%]]
+ [[lrand48 (C library)][67.5676][14.8][21%]]
+ [[minstd_rand0][96.1538][10.4][30%]]
+ [[minstd_rand][93.4579][10.7][29%]]
+ [[ecuyer combined][60.6061][16.5][19%]]
+ [[kreutzer1986][97.0874][10.3][31%]]
+ [[taus88][243.902][4.1][78%]]
+ [[hellekalek1995 (inversive)][2.405][415.8][0%]]
+ [[mt11213b][138.889][7.2][44%]]
+ [[mt19937][138.889][7.2][44%]]
+ [[lagged_fibonacci607][81.9672][12.2][26%]]
+ [[lagged_fibonacci1279][81.9672][12.2][26%]]
+ [[lagged_fibonacci2281][81.9672][12.2][26%]]
+ [[lagged_fibonacci3217][81.3008][12.3][26%]]
+ [[lagged_fibonacci4423][80.6452][12.4][25%]]
+ [[lagged_fibonacci9689][80.6452][12.4][25%]]
+ [[lagged_fibonacci19937][80][12.5][25%]]
+ [[lagged_fibonacci23209][80.6452][12.4][25%]]
+ [[lagged_fibonacci44497][79.3651][12.6][25%]]
+ [[subtract_with_carry][76.9231][13][24%]]
+ [[subtract_with_carry_01][45.045][22.2][14%]]
+ [[ranlux3][8.78735][113.8][2%]]
+ [[ranlux4][5.11771][195.4][1%]]
+ [[ranlux3_01][5.29381][188.9][1%]]
+ [[ranlux4_01][3.04599][328.3][0%]]
+ [[ranlux64_3][8.74126][114.4][2%]]
+ [[ranlux64_4][5.09684][196.2][1%]]
+ [[ranlux64_3_01][5.30786][188.4][1%]]
+ [[ranlux64_4_01][3.02847][330.2][0%]]
+ [[mt19937ar.c][95.2381][10.5][30%]]
+]
Added: trunk/libs/random/doc/generator_performance_windows.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/random/doc/generator_performance_windows.qbk 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -0,0 +1,33 @@
+[table Basic Generators (Windows)
+ [[generator] [M rn/sec] [time per random number \[nsec\]] [relative speed compared to fastest \[percent\]]]
+ [[rand48][98.5222][10.15][67%]]
+ [[lrand48 run-time][17.343][57.66][11%]]
+ [[minstd_rand0][46.3822][21.56][31%]]
+ [[minstd_rand][38.5505][25.94][26%]]
+ [[ecuyer combined][15.8028][63.28][10%]]
+ [[kreutzer1986][66.6667][15][45%]]
+ [[taus88][145.56][6.87][100%]]
+ [[hellekalek1995 (inversive)][4.26658][234.38][2%]]
+ [[mt11213b][139.082][7.19][95%]]
+ [[mt19937][142.248][7.03][97%]]
+ [[lagged_fibonacci607][61.5385][16.25][42%]]
+ [[lagged_fibonacci1279][58.7199][17.03][40%]]
+ [[lagged_fibonacci2281][64.0205][15.62][43%]]
+ [[lagged_fibonacci3217][62.1118][16.1][42%]]
+ [[lagged_fibonacci4423][63.3714][15.78][43%]]
+ [[lagged_fibonacci9689][64.6412][15.47][44%]]
+ [[lagged_fibonacci19937][63.3714][15.78][43%]]
+ [[lagged_fibonacci23209][64.6412][15.47][44%]]
+ [[lagged_fibonacci44497][64.0205][15.62][43%]]
+ [[subtract_with_carry][92.7644][10.78][63%]]
+ [[subtract_with_carry_01][78.0031][12.82][53%]]
+ [[ranlux3][9.86193][101.4][6%]]
+ [[ranlux4][5.80754][172.19][3%]]
+ [[ranlux3_01][7.15103][139.84][4%]]
+ [[ranlux4_01][3.8345][260.79][2%]]
+ [[ranlux64_3][9.10415][109.84][6%]]
+ [[ranlux64_4][5.05919][197.66][3%]]
+ [[ranlux64_3_01][6.12445][163.28][4%]]
+ [[ranlux64_4_01][3.39167][294.84][2%]]
+ [[mt19937ar.c][125.471][7.97][86%]]
+]
Added: trunk/libs/random/doc/generators.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/random/doc/generators.qbk 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -0,0 +1,80 @@
+This library provides several [prng pseudo-random number generators]. The
+quality of a [prng 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 boost::random`. Any particular choice of parameters is represented
+as the appropriately specializing `typedef` in `namespace boost`.
+
+[prng 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 [prng 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.
+
+Note that all [prng 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.
+
+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.
+
+[table generators
+ [[generator] [length of cycle] [approx. memory requirements] [approx. speed compared to fastest] [comment]]
+ [[__minstd_rand0] [2[sup 31]-2] [`sizeof(int32_t)`] [[minstd_rand0_speed]] [-]]
+ [[__minstd_rand] [2[sup 31]-2] [`sizeof(int32_t)`] [[minstd_rand_speed]] [-]]
+ [[__rand48][2[sup 48]-1] [`sizeof(uint64_t)`] [[rand48_speed]] [-]]
+ [[__ecuyer1988] [approx. 2[sup 61]] [`2*sizeof(int32_t)`] [[ecuyer_combined_speed]] [-]]
+ [[__kreutzer1986] [?] [`1368*sizeof(uint32_t)`] [[kreutzer1986_speed]] [-]]
+ [[__taus88] [~2[sup 88]] [`3*sizeof(uint32_t)`] [[taus88_speed]] [-]]
+ [[__hellekalek1995] [2[sup 31]-1] [`sizeof(int32_t)`] [[hellekalek1995__inversive__speed]] [good uniform distribution in several dimensions]]
+ [[__mt11213b] [2[sup 11213]-1] [`352*sizeof(uint32_t)`] [[mt11213b_speed]] [good uniform distribution in up to 350 dimensions]]
+ [[__mt19937] [2[sup 19937]-1] [`625*sizeof(uint32_t)`] [[mt19937_speed]] [good uniform distribution in up to 623 dimensions]]
+ [[__lagged_fibonacci607] [~2[sup 32000]] [`607*sizeof(double)`] [[lagged_fibonacci607_speed]] [-]]
+ [[__lagged_fibonacci1279] [~2[sup 67000]] [`1279*sizeof(double)`] [[lagged_fibonacci1279_speed]] [-]]
+ [[__lagged_fibonacci2281] [~2[sup 120000]] [`2281*sizeof(double)`] [[lagged_fibonacci2281_speed]] [-]]
+ [[__lagged_fibonacci3217] [~2[sup 170000]] [`3217*sizeof(double)`] [[lagged_fibonacci3217_speed]] [-]]
+ [[__lagged_fibonacci4423] [~2[sup 230000]] [`4423*sizeof(double)`] [[lagged_fibonacci4423_speed]] [-]]
+ [[__lagged_fibonacci9689] [~2[sup 510000]] [`9689*sizeof(double)`] [[lagged_fibonacci9689_speed]] [-]]
+ [[__lagged_fibonacci19937] [~2[sup 1050000]] [`19937*sizeof(double)`] [[lagged_fibonacci19937_speed]] [-]]
+ [[__lagged_fibonacci23209] [~2[sup 1200000]] [`23209*sizeof(double)`] [[lagged_fibonacci23209_speed]] [-]]
+ [[__lagged_fibonacci44497] [~2[sup 2300000]] [`44497*sizeof(double)`] [[lagged_fibonacci44497_speed]] [-]]
+ [[__ranlux3] [~10[sup 171]] [`24*sizeof(int)`] [[ranlux3_speed]] [-]]
+ [[__ranlux4] [~10[sup 171]] [`24*sizeof(int)`] [[ranlux4_speed]] [-]]
+ [[__ranlux64_3] [~10[sup 171]] [`24*sizeof(int64_t)`] [[ranlux64_3_speed]] [-]]
+ [[__ranlux64_4] [~10[sup 171]] [`24*sizeof(int64_t)`] [[ranlux64_4_speed]] [-]]
+ [[__ranlux3_01] [~10[sup 171]] [`24*sizeof(float)`] [[ranlux3_speed]] [-]]
+ [[__ranlux4_01] [~10[sup 171]] [`24*sizeof(float)`] [[ranlux4_speed]] [-]]
+ [[__ranlux64_3_01] [~10[sup 171]] [`24*sizeof(double)`] [[ranlux64_3_speed]] [-]]
+ [[__ranlux64_4_01] [~10[sup 171]] [`24*sizeof(double)`] [[ranlux64_4_speed]] [-]]
+]
+
+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.
+
+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 __mt19937 for a start: It
+is fast and has acceptable quality.
+
+[note These random number generators are not intended for use in applications
+where non-deterministic random numbers are required. See __random_device
+for a choice of (hopefully) non-deterministic random number generators.]
Added: trunk/libs/random/doc/nondet_random.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/random/doc/nondet_random.qbk 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -0,0 +1,95 @@
+[section Header <boost/nondet_random.hpp> Synopsis]
+
+ namespace boost {
+ class random_device;
+ } // namespace boost
+
+[endsect]
+
+[section Class random_device]
+
+[section Synopsis]
+
+ 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()();
+ };
+
+[endsect]
+
+[section Description]
+
+Class `random_device` models a non-deterministic random number generator. 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 random_device must not be implemented. See
+
+[:"Randomness Recommendations for Security", D. Eastlake, S. Crocker,
+J. Schiller, Network Working Group, RFC 1750, December 1994]
+
+for further discussions.
+
+[note 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.]
+
+[endsect]
+
+[section Members]
+
+ explicit random_device(const std::string& token = default_token)
+
+Effects: Constructs a random_device, optionally using the given token as an
+access specification (for example, a URL) to some implementation-defined
+service for monitoring a stochastic process.
+
+ double entropy() const
+
+Returns: An entropy estimate for the random numbers returned by `operator()`,
+in the range `min()` to `log2(max()+1)`. A deterministic random number
+generator (e.g. a pseudo-random number engine) has entropy 0.
+
+Throws: Nothing.
+
+[endsect]
+
+Implementation Note for Linux
+On the Linux operating system, token 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, std::ios_base::failure
+is thrown. By default, random_device uses the /dev/urandom pseudo-device to
+retrieve the random numbers. Another option would be to specify the
+/dev/random pseudo-device, which blocks on reads if the entropy pool has no
+more random bits available.
+
+[endsect]
+
+[section Performance]
+
+The test program nondet_random_speed.cpp measures the execution times of the
+nondet_random.hpp 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.
+
+[table preformance
+ [[class] [time per invocation \[usec\]]]
+ [[random_device] [92.0]]
+]
+
+The measurement error is estimated at +/- 1 usec.
+
+[endsect]
Added: trunk/libs/random/doc/performance.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/random/doc/performance.qbk 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -0,0 +1,22 @@
+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.
+
+The performance has been evaluated on an Intel(R) Xeon(TM) MP
+CPU 3.66GHz, Gentoo Base System release 1.12.11.1, GCC 4.3.2,
+glibc 2.9 and on an Intel(R) Core(TM)2 CPU T7600
+@2.33 Ghz with Microsoft Windows XP Professional, Service Pack 2 Build
+2600, Microsoft Visual C++ 2008 9.0.21022.
+The speed is reported in million random numbers
+per second (M rn/sec), generated in a tight loop.
+
+[include generator_performance_linux.qbk]
+[include generator_performance_windows.qbk]
+
+Note that the lagged Fibonacci and ranlux_01 generators produce
+floating-point numbers, whereas all others produce integers.
+
+[include distribution_performance_linux.qbk]
+[include distribution_performance_windows.qbk]
Added: trunk/libs/random/doc/performance_data.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/random/doc/performance_data.qbk 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -0,0 +1,31 @@
+[template rand48_speed[] 100%]
+[template lrand48_run_time_speed[] 96%]
+[template lrand48__C_library__speed[] 21%]
+[template minstd_rand0_speed[] 30%]
+[template minstd_rand_speed[] 29%]
+[template ecuyer_combined_speed[] 19%]
+[template kreutzer1986_speed[] 31%]
+[template taus88_speed[] 78%]
+[template hellekalek1995__inversive__speed[] 0%]
+[template mt11213b_speed[] 44%]
+[template mt19937_speed[] 44%]
+[template lagged_fibonacci607_speed[] 26%]
+[template lagged_fibonacci1279_speed[] 26%]
+[template lagged_fibonacci2281_speed[] 26%]
+[template lagged_fibonacci3217_speed[] 26%]
+[template lagged_fibonacci4423_speed[] 25%]
+[template lagged_fibonacci9689_speed[] 25%]
+[template lagged_fibonacci19937_speed[] 25%]
+[template lagged_fibonacci23209_speed[] 25%]
+[template lagged_fibonacci44497_speed[] 25%]
+[template subtract_with_carry_speed[] 24%]
+[template subtract_with_carry_01_speed[] 14%]
+[template ranlux3_speed[] 2%]
+[template ranlux4_speed[] 1%]
+[template ranlux3_01_speed[] 1%]
+[template ranlux4_01_speed[] 0%]
+[template ranlux64_3_speed[] 2%]
+[template ranlux64_4_speed[] 1%]
+[template ranlux64_3_01_speed[] 1%]
+[template ranlux64_4_01_speed[] 0%]
+[template mt19937ar_c_speed[] 30%]
Added: trunk/libs/random/doc/random.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/random/doc/random.qbk 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -0,0 +1,167 @@
+[library Boost.Random
+ [quickbook 1.5]
+ [authors [Maurer, Jens]]
+ [copyright 2000-2005 Jens Maurer, 2009 Steven Watanabe]
+ [license
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENSE_1_0.txt or copy at
+ [@http://www.boost.org/LICENSE_1_0.txt])
+ ]
+ [purpose A complete system for random number generation]
+]
+
+[template sup[text]'''<superscript>'''[text]'''</superscript>''']
+
+[template prng[text] [link boost_random.reference.concepts.pseudo_random_number_generator [text]]]
+[template concepts[text] [link boost_random.reference.concepts [text]]]
+[template generators[text] [link boost_random.reference.generators [text]]]
+[template distributions[text] [link boost_random.reference.distributions [text]]]
+
+[def __NumberGenerator [link boost_random.reference.concepts.number_generator NumberGenerator]]
+[def __UniformRandomNumberGenerator [link boost_random.reference.concepts.uniform_random_number_generator UniformRandomNumberGenerator]]
+
+[def __CopyConstructible [@boost:/doc/html/CopyConstructible.html CopyConstructible]]
+[def __Assignable [@boost:/doc/html/Assignable.html Assignable]]
+[def __LessThanComparable [@boost:/doc/html/LessThanComparable.html LessThanComparable]]
+[def __EqualityComparable [@boost:/doc/html/EqualityComparable.html EqualityComparable]]
+[def __Streamable Streamable]
+
+[def __random_device [classref boost::random_device random_device]]
+[def __random_number_generator [classref boost::random_number_generator random_number_generator]]
+[def __variate_generator [classref boost::variate_generator variate_generator]]
+
+[def __minstd_rand0 [classref boost::minstd_rand0 minstd_rand0]]
+[def __minstd_rand [classref boost::minstd_rand minstd_rand]]
+[def __rand48 [classref boost::rand48 rand48]]
+[def __ecuyer1988 [classref boost::ecuyer1988 ecuyer1988]]
+[def __kreutzer1986 [classref boost::kreutzer1986 kreutzer1986]]
+[def __taus88 [classref boost::taus88 taus88]]
+[def __hellekalek1995 [classref boost::hellekalek1995 hellekalek1995]]
+[def __mt11213b [classref boost::mt11213b mt11213b]]
+[def __mt19937 [classref boost::mt19937 mt19937]]
+[def __lagged_fibonacci607 [classref boost::lagged_fibonacci607 lagged_fibonacci607]]
+[def __lagged_fibonacci1279 [classref boost::lagged_fibonacci1279 lagged_fibonacci1279]]
+[def __lagged_fibonacci2281 [classref boost::lagged_fibonacci2281 lagged_fibonacci2281]]
+[def __lagged_fibonacci3217 [classref boost::lagged_fibonacci3217 lagged_fibonacci3217]]
+[def __lagged_fibonacci4423 [classref boost::lagged_fibonacci4423 lagged_fibonacci4423]]
+[def __lagged_fibonacci9689 [classref boost::lagged_fibonacci9689 lagged_fibonacci9689]]
+[def __lagged_fibonacci19937 [classref boost::lagged_fibonacci19937 lagged_fibonacci19937]]
+[def __lagged_fibonacci23209 [classref boost::lagged_fibonacci23209 lagged_fibonacci23209]]
+[def __lagged_fibonacci44497 [classref boost::lagged_fibonacci44497 lagged_fibonacci44497]]
+[def __ranlux3 [classref boost::ranlux3 ranlux3]]
+[def __ranlux4 [classref boost::ranlux4 ranlux4]]
+[def __ranlux64_3 [classref boost::ranlux64_3 ranlux64_3]]
+[def __ranlux64_4 [classref boost::ranlux64_4 ranlux64_4]]
+[def __ranlux3_01 [classref boost::ranlux3_01 ranlux3_01]]
+[def __ranlux4_01 [classref boost::ranlux4_01 ranlux4_01]]
+[def __ranlux64_3_01 [classref boost::ranlux64_3_01 ranlux64_3_01]]
+[def __ranlux64_4_01 [classref boost::ranlux64_4_01 ranlux64_4_01]]
+
+[def __uniform_smallint [classref boost::uniform_smallint uniform_smallint]]
+[def __uniform_int [classref boost::uniform_int uniform_int]]
+[def __uniform_01 [classref boost::uniform_01 uniform_01]]
+[def __uniform_real [classref boost::uniform_real uniform_real]]
+[def __bernoulli_distribution [classref boost::bernoulli_distribution bernoulli_distribution]]
+[def __binomial_distribution [classref boost::binomial_distribution binomial_distribution]]
+[def __cauchy_distribution [classref boost::cauchy_distribution cauchy_distribution]]
+[def __gamma_distribution [classref boost::gamma_distribution gamma_distribution]]
+[def __poisson_distribution [classref boost::poisson_distribution poisson_distribution]]
+[def __geometric_distribution [classref boost::geometric_distribution geometric_distribution]]
+[def __triangle_distribution [classref boost::triangle_distribution triangle_distribution]]
+[def __exponential_distribution [classref boost::exponential_distribution exponential_distribution]]
+[def __normal_distribution [classref boost::normal_distribution normal_distribution]]
+[def __lognormal_distribution [classref boost::lognormal_distribution lognormal_distribution]]
+[def __uniform_on_sphere [classref boost::uniform_on_sphere uniform_on_sphere]]
+
+[include performance_data.qbk]
+
+[section Introduction]
+
+Random numbers are useful in a variety of applications. The Boost Random
+Number Library (Boost.Random for short) provides a variety of
+[generators generators] and [distributions distributions] to produce
+random numbers having useful properties, such as uniform distribution.
+
+You should read the [concepts concepts documentation] for an introduction and the
+definition of the basic concepts. For a quick start, it may be sufficient
+to have a look at [@boost:/libs/random/random_demo.cpp random_demo.cpp].
+
+For a very quick start, here's an example:
+
+ ``[classref boost::mt19937]`` rng; // produces randomness out of thin air
+ // see pseudo-random number generators
+ ``[classref boost::uniform_int]<>`` six(1,6); // distribution that maps to 1..6
+ // see random number distributions
+ ``[classref boost::variate_generator]``<``[classref boost::mt19937]``&, ``[classref boost::uniform_int]``<> >
+ die(rng, six); // glues randomness with mapping
+ int x = die(); // simulate rolling a die
+
+[endsect]
+
+[section Tutorial]
+[include tutorial.qbk]
+[endsect]
+
+[section Reference]
+
+[section Concepts]
+[include concepts.qbk]
+[endsect]
+
+[section Generators]
+[include generators.qbk]
+[endsect]
+
+[section Distributions]
+[include distributions.qbk]
+[endsect]
+
+[xinclude reference.xml]
+
+[endsect]
+
+[section Performance]
+[include performance.qbk]
+[endsect]
+
+[section Rationale]
+
+The methods for generating and evaluating deterministic and non-deterministic
+random numbers differ radically. Furthermore, due to the inherent
+deterministic design of present-day computers, it is often difficult to
+implement non-deterministic random number generation facilities. Thus, the
+random number library is split into separate header files, mirroring the two
+different application domains.
+
+[endsect]
+
+[section History and Acknowledgements]
+
+In November 1999, Jeet Sukumaran proposed a framework based on virtual
+functions, and later sketched a template-based approach. Ed Brey pointed
+out that Microsoft Visual C++ does not support in-class member
+initializations and suggested the enum workaround. Dave Abrahams highlighted
+quantization issues.
+
+The first public release of this random number library materialized in
+March 2000 after extensive discussions on the boost mailing list. Many
+thanks to Beman Dawes for his original min_rand class, portability fixes,
+documentation suggestions, and general guidance. Harry Erwin sent a header
+file which provided additional insight into the requirements. Ed Brey and
+Beman Dawes wanted an iterator-like interface.
+
+Beman Dawes managed the formal review, during which Matthias Troyer,
+Csaba Szepesvari, and Thomas Holenstein gave detailed comments. The
+reviewed version became an official part of boost on 17 June 2000.
+
+Gary Powell contributed suggestions for code cleanliness. Dave Abrahams
+and Howard Hinnant suggested to move the basic generator templates from
+`namespace boost::detail` to `boost::random`.
+
+Ed Brey asked to remove superfluous warnings and helped with `uint64_t`
+handling. Andreas Scherer tested with MSVC. Matthias Troyer contributed
+a [headerref boost/random/lagged_fibonacci.hpp lagged Fibonacci generator].
+Michael Stevens found a bug in the copy semantics of __normal_distribution
+and suggested documentation improvements.
+
+[endsect]
Added: trunk/libs/random/doc/random_number_generator.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/random/doc/random_number_generator.qbk 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -0,0 +1,53 @@
+[section Synopsis of miscellaneous decorators in header <boost/random.hpp>]
+
+ namespace boost {
+ template<class UniformRandomNumberGenerator, class IntType = long>
+ class random_number_generator;
+ } // namespace boost
+
+[endsect]
+
+[section Class template random_number_generator]
+
+[section Synopsis]
+
+ 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);
+ };
+
+[endsect]
+
+[section Description]
+
+Instantiations of class template random_number_generator model a
+RandomNumberGenerator (std:25.2.11 [lib.alg.random.shuffle]). On each
+invocation, it returns a uniformly distributed integer in the range [0..n).
+
+The template parameter IntType shall denote some integer-like value type.
+
+[note I consider it unfortunate that the C++ Standard uses the name
+RandomNumberGenerator for something rather specific.]
+
+[endsect]
+
+[section Members]
+
+ random_number_generator(base_type & rng)
+
+Effects: Constructs a random_number_generator functor with the given uniform
+random number generator as the underlying source of random numbers.
+
+ result_type operator()(argument_type n)
+
+Returns: The value of uniform_int<base_type>(rng, 0, n-1)().
+
+[endsect]
+
+[endsect]
Added: trunk/libs/random/doc/tutorial.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/random/doc/tutorial.qbk 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -0,0 +1,13 @@
+[section Generating integers in a range]
+
+[import ../example/die.cpp]
+[die]
+
+[endsect]
+
+[section Generating integers with different probabilities]
+
+[import ../example/weighted_die.cpp]
+[weighted_die]
+
+[endsect]
Added: trunk/libs/random/example/Jamfile.v2
==============================================================================
--- (empty file)
+++ trunk/libs/random/example/Jamfile.v2 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -0,0 +1,11 @@
+# Jamfile.v2
+#
+# Copyright (c) 2009
+# Steven Watanabe
+#
+# Distributed under the Boost Software License, Version 1.0. (See
+# accompanying file LICENSE_1_0.txt or copy at
+# http://www.boost.org/LICENSE_1_0.txt)
+
+run die.cpp ;
+run weighted_die.cpp ;
Added: trunk/libs/random/example/die.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/random/example/die.cpp 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -0,0 +1,59 @@
+//[die
+/*`
+ For the source of this example see
+ [@boost://libs/random/example/die.cpp die.cpp].
+ First we include the headers we need for __mt19937
+ and __uniform_int.
+*/
+#include <boost/random/mersenne_twister.hpp>
+#include <boost/random/uniform_int.hpp>
+#include <boost/random/variate_generator.hpp>
+
+/*`
+ We use __mt19937 with the default seed as a source of
+ randomness. The numbers produced will be the same
+ every time the program is run. One common method to
+ change this is to seed with the current time (`std::time(0)`
+ defined in ctime).
+*/
+boost::mt19937 gen;
+/*`
+ [note We are using a /global/ generator object here. This
+ is important because we don't want to create a new [prng
+ pseudo-random number generator] at every call]
+*/
+/*`
+ Now we can define a function that simulates an ordinary
+ six-sided die.
+*/
+int roll_die() {
+ /*<< __mt19937 produces integers in the range [0, 2[sup 32]-1].
+ However, we want numbers in the range [1, 6]. The distribution
+ __uniform_int performs this transformation.
+ [warning Contrary to common C++ usage __uniform_int
+ does not take a /half-open range/. Instead it takes a /closed range/.
+ Given the parameters 1 and 6, __uniform_int can
+ can produce any of the values 1, 2, 3, 4, 5, or 6.]
+ >>*/
+ boost::uniform_int<> dist(1, 6);
+ /*<< __variate_generator combines a generator with a distribution.
+ [important We pass [classref boost::mt19937 boost::mt19937&] to
+ __variate_generator instead of just [classref boost::mt19937]
+ (note the reference). Without the reference, __variate_generator
+ would make a copy of the generator and would leave the global
+ `gen` unchanged. Consequently, `roll_die` would produce *the same value*
+ every time it was called.]
+ >>*/
+ boost::variate_generator<boost::mt19937&, boost::uniform_int<> > die(gen, dist);
+ /*<< A __variate_generator is a function object. >>*/
+ return die();
+}
+//]
+
+#include <iostream>
+
+int main() {
+ for(int i = 0; i < 10; ++i) {
+ std::cout << roll_die() << std::endl;
+ }
+}
Added: trunk/libs/random/example/weighted_die.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/random/example/weighted_die.cpp 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -0,0 +1,50 @@
+//[weighted_die
+/*`
+ For the source of this example see
+ [@boost://libs/random/example/weighted_die.cpp weighted_die.cpp].
+*/
+#include <boost/random/mersenne_twister.hpp>
+#include <boost/random/uniform_real.hpp>
+#include <boost/random/variate_generator.hpp>
+#include <vector>
+#include <algorithm>
+#include <numeric>
+
+boost::mt19937 gen;
+
+/*`
+ This time, instead of a fair die, the probability of
+ rolling a 1 is 50% (!). The other five faces are all
+ equally likely.
+*/
+static const double probabilities[] = {
+ 0.5, 0.1, 0.1, 0.1, 0.1, 0.1
+};
+
+/*`
+ Now define a function that simulates rolling this die.
+ Note that the C++0x library contains a `discrete_distribution`
+ class which would be a better way to do this.
+*/
+int roll_weighted_die() {
+ std::vector<double> cumulative;
+ std::partial_sum(&probabilities[0], &probabilities[0] + 6,
+ std::back_inserter(cumulative));
+ boost::uniform_real<> dist(0, cumulative.back());
+ boost::variate_generator<boost::mt19937&, boost::uniform_real<> > die(gen, dist);
+ /*<< Find the position within the sequence and add 1
+ (to make sure that the result is in the range [1,6]
+ instead of [0,5])
+ >>*/
+ return (std::lower_bound(cumulative.begin(), cumulative.end(), die()) - cumulative.begin()) + 1;
+}
+
+//]
+
+#include <iostream>
+
+int main() {
+ for(int i = 0; i < 10; ++i) {
+ std::cout << roll_weighted_die() << std::endl;
+ }
+}
Added: trunk/libs/random/generate_table.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/random/generate_table.cpp 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -0,0 +1,121 @@
+// generate_table.cpp
+//
+// Copyright (c) 2009
+// Steven Watanabe
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#include <vector>
+#include <utility>
+#include <iostream>
+#include <cstring>
+#include <fstream>
+#include <boost/regex.hpp>
+#include <boost/tuple/tuple.hpp>
+#include <boost/lexical_cast.hpp>
+#include <boost/foreach.hpp>
+#include <boost/format.hpp>
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/hashed_index.hpp>
+#include <boost/multi_index/sequenced_index.hpp>
+
+boost::regex generator_regex("(?:fixed-range )?([^:]+): (\\d+(?:\\.\\d+)?) nsec/loop = \\d+(?:\\.\\d+)? CPU cycles");
+boost::regex distribution_regex("([^\\s]+)( virtual function)? ([^:]+): (\\d+(?:\\.\\d+)?) nsec/loop = \\d+(?:\\.\\d+)? CPU cycles");
+
+std::string template_name(std::string arg) {
+ return boost::regex_replace(arg, boost::regex("[^\\w]"), "_");
+}
+
+struct compare_second {
+ template<class Pair>
+ bool operator()(const Pair& p1, const Pair& p2) const {
+ return (p1.second < p2.second);
+ }
+};
+
+typedef boost::multi_index_container<
+ std::string,
+ boost::mpl::vector<
+ boost::multi_index::sequenced<>,
+ boost::multi_index::hashed_unique<boost::multi_index::identity<std::string> >
+ >
+> unique_list;
+
+int main() {
+ std::vector<std::pair<std::string, double> > generator_info;
+ std::string line;
+ while(std::getline(std::cin, line)) {
+ boost::smatch match;
+ if(std::strncmp(line.c_str(), "counting ", 9) == 0) break;
+ if(boost::regex_match(line, match, generator_regex)) {
+ std::string generator(match[1]);
+ double time = boost::lexical_cast<double>(match[2]);
+ if(generator != "counting") {
+ generator_info.push_back(std::make_pair(generator, time));
+ }
+ } else {
+ std::cerr << "oops: " << line << std::endl;
+ }
+ }
+
+ double min = std::min_element(generator_info.begin(), generator_info.end(), compare_second())->second;
+
+ std::ofstream generator_defs("performance_data.qbk");
+ std::ofstream generator_performance("generator_performance.qbk");
+ generator_performance << "[table Basic Generators\n";
+ generator_performance << " [[generator] [M rn/sec] [time per random number \\[nsec\\]] "
+ "[relative speed compared to fastest \\[percent\\]]]\n";
+
+ typedef std::pair<std::string, double> pair_type;
+ BOOST_FOREACH(const pair_type& pair, generator_info) {
+ generator_defs << boost::format("[template %s_speed[] %d%%]\n")
+ % template_name(pair.first) % static_cast<int>(100*min/pair.second);
+ generator_performance << boost::format(" [[%s][%g][%g][%d%%]]\n")
+ % pair.first % (1000/pair.second) % pair.second % static_cast<int>(100*min/pair.second);
+ }
+ generator_performance << "]\n";
+
+ std::map<std::pair<std::string, std::string>, double> distribution_info;
+ unique_list generator_names;
+ unique_list distribution_names;
+ do {
+ boost::smatch match;
+ if(boost::regex_match(line, match, distribution_regex)) {
+ if(!match[2].matched && match[1] != "counting") {
+ std::string generator(match[1]);
+ std::string distribution(match[3]);
+ double time = boost::lexical_cast<double>(match[4]);
+ generator_names.push_back(generator);
+ distribution_names.push_back(distribution);
+ distribution_info.insert(std::make_pair(std::make_pair(distribution, generator), time));
+ }
+ } else {
+ std::cerr << "oops: " << line << std::endl;
+ }
+ } while(std::getline(std::cin, line));
+
+ std::ofstream distribution_performance("distribution_performance.qbk");
+
+ distribution_performance << "[table Distributions\n";
+ distribution_performance << " [[\\[M rn/sec\\]]";
+ BOOST_FOREACH(const std::string& generator, generator_names) {
+ distribution_performance << boost::format("[%s]") % generator;
+ }
+ distribution_performance << "]\n";
+ BOOST_FOREACH(const std::string& distribution, distribution_names) {
+ distribution_performance << boost::format(" [[%s]") % distribution;
+ BOOST_FOREACH(const std::string& generator, generator_names) {
+ std::map<std::pair<std::string, std::string>, double>::iterator pos =
+ distribution_info.find(std::make_pair(distribution, generator));
+ if(pos != distribution_info.end()) {
+ distribution_performance << boost::format("[%g]") % (1000/pos->second);
+ } else {
+ distribution_performance << "[-]";
+ }
+ }
+ distribution_performance << "]\n";
+ }
+ distribution_performance << "]\n";
+}
Modified: trunk/libs/random/random_speed.cpp
==============================================================================
--- trunk/libs/random/random_speed.cpp (original)
+++ trunk/libs/random/random_speed.cpp 2010-02-25 13:13:36 EST (Thu, 25 Feb 2010)
@@ -21,13 +21,16 @@
*/
// define if your C library supports the non-standard drand48 family
-#undef HAVE_DRAND48
+#define HAVE_DRAND48
// define if you have the original mt19937int.c (with commented out main())
#undef HAVE_MT19937INT_C
+// define if you have the original mt19937ar.c (with commented out main())
+#define HAVE_MT19937AR_C
+
// set to your CPU frequency in MHz
-static const double cpu_frequency = 200 * 1e6;
+static const double cpu_frequency = 3.66 * 1e9;
/*
* End of Configuration Section
@@ -173,20 +176,33 @@
}
template<class RNG>
-void run(int iter, const std::string & name, const RNG &)
+void run(int iter, const std::string & name, RNG rng)
{
std::cout << (RNG::has_fixed_range ? "fixed-range " : "");
// BCC has trouble with string autoconversion for explicit specializations
- timing(RNG(), iter, std::string(name));
+
+ // make sure we're not optimizing too much
+ volatile typename RNG::result_type tmp;
+ boost::timer t;
+ for(int i = 0; i < iter; i++)
+ tmp = rng();
+ show_elapsed(t.elapsed(), iter, name);
}
#ifdef HAVE_DRAND48
// requires non-standard C library support for srand48/lrand48
-void run(int iter, const std::string & name, int)
-{
- std::srand48(1);
- timing(&std::lrand48, iter, name);
-}
+struct lrand48_ {
+ static const bool has_fixed_range = false;
+ typedef long result_type;
+ lrand48_() {
+ using namespace std;
+ srand48(1);
+ }
+ result_type operator()() {
+ using namespace std;
+ return lrand48();
+ }
+};
#endif
#ifdef HAVE_MT19937INT_C // requires the original mt19937int.c
@@ -200,6 +216,23 @@
}
#endif
+#ifdef HAVE_MT19937AR_C
+extern "C" {
+void init_genrand(unsigned long s);
+unsigned long genrand_int32(void);
+}
+struct mt19937_c {
+ static const bool has_fixed_range = false;
+ mt19937_c() {
+ init_genrand(5489);
+ }
+ typedef unsigned long result_type;
+ result_type operator()() {
+ return genrand_int32();
+ }
+};
+#endif
+
template<class PRNG, class Dist>
inline boost::variate_generator<PRNG&, Dist> make_gen(PRNG & rng, Dist d)
{
@@ -329,24 +362,41 @@
#ifdef HAVE_DRAND48
// requires non-standard C library support for srand48/lrand48
- run(iter, "lrand48", 0); // coded for lrand48()
+ run(iter, "lrand48", lrand48_()); // coded for lrand48()
#endif
+ run(iter, "minstd_rand0", boost::minstd_rand0());
run(iter, "minstd_rand", boost::minstd_rand());
run(iter, "ecuyer combined", boost::ecuyer1988());
run(iter, "kreutzer1986", boost::kreutzer1986());
+ run(iter, "taus88", boost::taus88());
run(iter, "hellekalek1995 (inversive)", boost::hellekalek1995());
run(iter, "mt11213b", boost::mt11213b());
run(iter, "mt19937", boost::mt19937());
+ run(iter, "lagged_fibonacci607", boost::lagged_fibonacci607());
+ run(iter, "lagged_fibonacci1279", boost::lagged_fibonacci1279());
+ run(iter, "lagged_fibonacci2281", boost::lagged_fibonacci2281());
+ run(iter, "lagged_fibonacci3217", boost::lagged_fibonacci3217());
+ run(iter, "lagged_fibonacci4423", boost::lagged_fibonacci4423());
+ run(iter, "lagged_fibonacci9689", boost::lagged_fibonacci9689());
+ run(iter, "lagged_fibonacci19937", boost::lagged_fibonacci19937());
+ run(iter, "lagged_fibonacci23209", boost::lagged_fibonacci23209());
+ run(iter, "lagged_fibonacci44497", boost::lagged_fibonacci44497());
+
run(iter, "subtract_with_carry", boost::random::ranlux_base());
run(iter, "subtract_with_carry_01", boost::random::ranlux_base_01());
run(iter, "ranlux3", boost::ranlux3());
run(iter, "ranlux4", boost::ranlux4());
run(iter, "ranlux3_01", boost::ranlux3_01());
run(iter, "ranlux4_01", boost::ranlux4_01());
+ run(iter, "ranlux64_3", boost::ranlux3());
+ run(iter, "ranlux64_4", boost::ranlux4());
+ run(iter, "ranlux64_3_01", boost::ranlux3_01());
+ run(iter, "ranlux64_4_01", boost::ranlux4_01());
+
run(iter, "counting", counting());
#ifdef HAVE_MT19937INT_C
@@ -354,6 +404,10 @@
run<float>(iter, "mt19937 original"); // coded for sgenrand()/genrand()
#endif
+#ifdef HAVE_MT19937AR_C
+ run(iter, "mt19937ar.c", mt19937_c());
+#endif
+
distrib(iter, "counting", counting());
distrib_runtime(iter, "counting", counting());
@@ -362,5 +416,8 @@
distrib(iter, "kreutzer1986", boost::kreutzer1986());
distrib(iter, "mt19937", boost::mt19937());
+
+ distrib(iter, "lagged_fibonacci607", boost::lagged_fibonacci607());
+
distrib_runtime(iter, "mt19937", boost::mt19937());
}
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