Subject: [Boost-commit] svn:boost r53871 - in branches/release: boost/random boost/random/detail libs/random
From: steven_at_[hidden]
Date: 2009-06-13 13:54:08
Author: steven_watanabe
Date: 2009-06-13 13:54:06 EDT (Sat, 13 Jun 2009)
New Revision: 53871
URL: http://svn.boost.org/trac/boost/changeset/53871
Log:
Merge [53462], [53699], and [53800] from the trunk.
Added:
branches/release/boost/random/detail/seed.hpp
- copied unchanged from r53699, /trunk/boost/random/detail/seed.hpp
Text files modified:
branches/release/boost/random/additive_combine.hpp | 8 ++
branches/release/boost/random/discard_block.hpp | 1
branches/release/boost/random/lagged_fibonacci.hpp | 14 ++-
branches/release/boost/random/linear_congruential.hpp | 22 ++++-
branches/release/boost/random/mersenne_twister.hpp | 22 +----
branches/release/boost/random/subtract_with_carry.hpp | 14 ++-
branches/release/boost/random/uniform_int.hpp | 134 ++++++++++++++++++++++++++++++++-------
branches/release/boost/random/xor_combine.hpp | 3
branches/release/libs/random/instantiate.cpp | 55 +++++++++++++++
branches/release/libs/random/random-generators.html | 109 ++++++++++++++-----------------
branches/release/libs/random/random_test.cpp | 34 +++++++++
11 files changed, 295 insertions(+), 121 deletions(-)
Modified: branches/release/boost/random/additive_combine.hpp
==============================================================================
--- branches/release/boost/random/additive_combine.hpp (original)
+++ branches/release/boost/random/additive_combine.hpp 2009-06-13 13:54:06 EDT (Sat, 13 Jun 2009)
@@ -54,6 +54,8 @@
additive_combine(typename MLCG1::result_type seed1,
typename MLCG2::result_type seed2)
: _mlcg1(seed1), _mlcg2(seed2) { }
+ additive_combine(result_type seed)
+ : _mlcg1(seed), _mlcg2(seed) { }
template<class It> additive_combine(It& first, It last)
: _mlcg1(first, last), _mlcg2(first, last) { }
@@ -63,6 +65,12 @@
_mlcg2.seed();
}
+ void seed(result_type seed)
+ {
+ _mlcg1.seed(seed);
+ _mlcg2.seed(seed);
+ }
+
void seed(typename MLCG1::result_type seed1,
typename MLCG2::result_type seed2)
{
Modified: branches/release/boost/random/discard_block.hpp
==============================================================================
--- branches/release/boost/random/discard_block.hpp (original)
+++ branches/release/boost/random/discard_block.hpp 2009-06-13 13:54:06 EDT (Sat, 13 Jun 2009)
@@ -43,6 +43,7 @@
discard_block() : _rng(), _n(0) { }
explicit discard_block(const base_type & rng) : _rng(rng), _n(0) { }
+ template<class T> explicit discard_block(T s) : _rng(s), _n(0) {}
template<class It> discard_block(It& first, It last)
: _rng(first, last), _n(0) { }
void seed() { _rng.seed(); _n = 0; }
Modified: branches/release/boost/random/lagged_fibonacci.hpp
==============================================================================
--- branches/release/boost/random/lagged_fibonacci.hpp (original)
+++ branches/release/boost/random/lagged_fibonacci.hpp 2009-06-13 13:54:06 EDT (Sat, 13 Jun 2009)
@@ -28,6 +28,7 @@
#include <boost/random/linear_congruential.hpp>
#include <boost/random/uniform_01.hpp>
#include <boost/random/detail/config.hpp>
+#include <boost/random/detail/seed.hpp>
#include <boost/random/detail/pass_through_engine.hpp>
namespace boost {
@@ -267,9 +268,10 @@
BOOST_STATIC_CONSTANT(unsigned int, short_lag = q);
lagged_fibonacci_01() { init_modulus(); seed(); }
- explicit lagged_fibonacci_01(uint32_t value) { init_modulus(); seed(value); }
- template<class Generator>
- explicit lagged_fibonacci_01(Generator & gen) { init_modulus(); seed(gen); }
+ BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(lagged_fibonacci_01, uint32_t, value)
+ { init_modulus(); seed(value); }
+ BOOST_RANDOM_DETAIL_GENERATOR_CONSTRUCTOR(lagged_fibonacci_01, Generator, gen)
+ { init_modulus(); seed(gen); }
template<class It> lagged_fibonacci_01(It& first, It last)
{ init_modulus(); seed(first, last); }
// compiler-generated copy ctor and assignment operator are fine
@@ -285,7 +287,8 @@
}
public:
- void seed(uint32_t value = 331u)
+ void seed() { seed(331u); }
+ BOOST_RANDOM_DETAIL_ARITHMETIC_SEED(lagged_fibonacci_01, uint32_t, value)
{
minstd_rand0 intgen(value);
seed(intgen);
@@ -294,8 +297,7 @@
// 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.
- template<class Generator>
- void seed(Generator & gen)
+ BOOST_RANDOM_DETAIL_GENERATOR_SEED(lagged_fibonacci, Generator, gen)
{
// use pass-by-reference, but wrap argument in pass_through_engine
typedef detail::pass_through_engine<Generator&> ref_gen;
Modified: branches/release/boost/random/linear_congruential.hpp
==============================================================================
--- branches/release/boost/random/linear_congruential.hpp (original)
+++ branches/release/boost/random/linear_congruential.hpp 2009-06-13 13:54:06 EDT (Sat, 13 Jun 2009)
@@ -212,12 +212,12 @@
int32_t min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return 0; }
int32_t max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return std::numeric_limits<int32_t>::max BOOST_PREVENT_MACRO_SUBSTITUTION (); }
- explicit rand48(int32_t x0 = 1) : lcf(cnv(x0)) { }
- explicit rand48(uint64_t x0) : lcf(x0) { }
+ rand48() : lcf(cnv(static_cast<int32_t>(1))) {}
+ template<class T> explicit rand48(T x0) : lcf(cnv(x0)) { }
template<class It> rand48(It& first, It last) : lcf(first, last) { }
// compiler-generated copy ctor and assignment operator are fine
- void seed(int32_t x0 = 1) { lcf.seed(cnv(x0)); }
- void seed(uint64_t x0) { lcf.seed(x0); }
+ void seed() { seed(static_cast<int32_t>(1)); }
+ template<class T> void seed(T x0) { lcf.seed(cnv(x0)); }
template<class It> void seed(It& first, It last) { lcf.seed(first,last); }
int32_t operator()() { return static_cast<int32_t>(lcf() >> 17); }
@@ -253,8 +253,18 @@
random::linear_congruential<uint64_t,
uint64_t(0xDEECE66DUL) | (uint64_t(0x5) << 32), // xxxxULL is not portable
0xB, uint64_t(1)<<48, /* unknown */ 0> lcf;
- static uint64_t cnv(int32_t x)
- { return (static_cast<uint64_t>(x) << 16) | 0x330e; }
+ template<class T>
+ static uint64_t cnv(T x)
+ {
+ if(sizeof(T) < sizeof(uint64_t)) {
+ return (static_cast<uint64_t>(x) << 16) | 0x330e;
+ } else {
+ return(static_cast<uint64_t>(x));
+ }
+ }
+ 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)); }
};
#endif /* !BOOST_NO_INT64_T && !BOOST_NO_INTEGRAL_INT64_T */
Modified: branches/release/boost/random/mersenne_twister.hpp
==============================================================================
--- branches/release/boost/random/mersenne_twister.hpp (original)
+++ branches/release/boost/random/mersenne_twister.hpp 2009-06-13 13:54:06 EDT (Sat, 13 Jun 2009)
@@ -28,6 +28,7 @@
#include <boost/detail/workaround.hpp>
#include <boost/random/detail/config.hpp>
#include <boost/random/detail/ptr_helper.hpp>
+#include <boost/random/detail/seed.hpp>
namespace boost {
namespace random {
@@ -55,28 +56,18 @@
mersenne_twister() { seed(); }
-#if defined(__SUNPRO_CC) && (__SUNPRO_CC <= 0x520)
- // Work around overload resolution problem (Gennadiy E. Rozental)
- explicit mersenne_twister(const UIntType& value)
-#else
- explicit mersenne_twister(UIntType value)
-#endif
+ BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(mersenne_twister, UIntType, value)
{ seed(value); }
template<class It> mersenne_twister(It& first, It last) { seed(first,last); }
- template<class Generator>
- explicit mersenne_twister(Generator & gen) { seed(gen); }
+ BOOST_RANDOM_DETAIL_GENERATOR_CONSTRUCTOR(mersenne_twister, Generator, gen)
+ { seed(gen); }
// compiler-generated copy ctor and assignment operator are fine
void seed() { seed(UIntType(5489)); }
-#if defined(__SUNPRO_CC) && (__SUNPRO_CC <= 0x520)
- // Work around overload resolution problem (Gennadiy E. Rozental)
- void seed(const UIntType& value)
-#else
- void seed(UIntType value)
-#endif
+ BOOST_RANDOM_DETAIL_ARITHMETIC_SEED(mersenne_twister, UIntType, value)
{
// New seeding algorithm from
// http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/emt19937ar.html
@@ -93,8 +84,7 @@
// 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.
- template<class Generator>
- void seed(Generator & gen)
+ BOOST_RANDOM_DETAIL_GENERATOR_SEED(mersenne_twister, Generator, gen)
{
#ifndef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS
BOOST_STATIC_ASSERT(!std::numeric_limits<result_type>::is_signed);
Modified: branches/release/boost/random/subtract_with_carry.hpp
==============================================================================
--- branches/release/boost/random/subtract_with_carry.hpp (original)
+++ branches/release/boost/random/subtract_with_carry.hpp 2009-06-13 13:54:06 EDT (Sat, 13 Jun 2009)
@@ -27,6 +27,7 @@
#include <boost/static_assert.hpp>
#include <boost/detail/workaround.hpp>
#include <boost/random/detail/config.hpp>
+#include <boost/random/detail/seed.hpp>
#include <boost/random/linear_congruential.hpp>
@@ -86,14 +87,16 @@
#endif
seed();
}
- explicit subtract_with_carry(uint32_t value) { seed(value); }
- template<class Generator>
- explicit subtract_with_carry(Generator & gen) { seed(gen); }
+ BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(subtract_with_carry, uint32_t, value)
+ { seed(value); }
+ BOOST_RANDOM_DETAIL_GENERATOR_CONSTRUCTOR(subtract_with_carry, Generator, gen)
+ { seed(gen); }
template<class It> subtract_with_carry(It& first, It last) { seed(first,last); }
// compiler-generated copy ctor and assignment operator are fine
- void seed(uint32_t value = 19780503u)
+ void seed() { seed(19780503u); }
+ BOOST_RANDOM_DETAIL_ARITHMETIC_SEED(subtract_with_carry, uint32_t, value)
{
random::linear_congruential<int32_t, 40014, 0, 2147483563, 0> intgen(value);
seed(intgen);
@@ -102,8 +105,7 @@
// 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.
- template<class Generator>
- void seed(Generator & gen)
+ BOOST_RANDOM_DETAIL_GENERATOR_SEED(subtract_with_carry, Generator, gen)
{
// I could have used std::generate_n, but it takes "gen" by value
for(unsigned int j = 0; j < long_lag; ++j)
Modified: branches/release/boost/random/uniform_int.hpp
==============================================================================
--- branches/release/boost/random/uniform_int.hpp (original)
+++ branches/release/boost/random/uniform_int.hpp 2009-06-13 13:54:06 EDT (Sat, 13 Jun 2009)
@@ -23,13 +23,9 @@
#include <boost/limits.hpp>
#include <boost/static_assert.hpp>
#include <boost/detail/workaround.hpp>
-#include <boost/random/uniform_smallint.hpp>
#include <boost/random/detail/config.hpp>
#include <boost/random/detail/signed_unsigned_tools.hpp>
#include <boost/type_traits/make_unsigned.hpp>
-#ifdef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS
-#include <boost/type_traits/is_float.hpp>
-#endif
namespace boost {
@@ -119,45 +115,135 @@
for(;;) {
// concatenate several invocations of the base RNG
// take extra care to avoid overflows
+
+ // limit == floor((range+1)/(brange+1))
+ // Therefore limit*(brange+1) <= range+1
range_type limit;
if(range == (std::numeric_limits<range_type>::max)()) {
limit = range/(range_type(brange)+1);
- if(range % range_type(brange)+1 == range_type(brange))
+ if(range % (range_type(brange)+1) == range_type(brange))
++limit;
} else {
limit = (range+1)/(range_type(brange)+1);
}
+
// We consider "result" as expressed to base (brange+1):
// For every power of (brange+1), we determine a random factor
range_type result = range_type(0);
range_type mult = range_type(1);
+
+ // loop invariants:
+ // result < mult
+ // mult <= range
while(mult <= limit) {
+ // Postcondition: result <= range, thus no overflow
+ //
+ // limit*(brange+1)<=range+1 def. of limit (1)
+ // eng()-bmin<=brange eng() post. (2)
+ // and mult<=limit. loop condition (3)
+ // Therefore mult*(eng()-bmin+1)<=range+1 by (1),(2),(3) (4)
+ // Therefore mult*(eng()-bmin)+mult<=range+1 rearranging (4) (5)
+ // result<mult loop invariant (6)
+ // Therefore result+mult*(eng()-bmin)<range+1 by (5), (6) (7)
+ //
+ // Postcondition: result < mult*(brange+1)
+ //
+ // result<mult loop invariant (1)
+ // eng()-bmin<=brange eng() post. (2)
+ // Therefore result+mult*(eng()-bmin) <
+ // mult+mult*(eng()-bmin) by (1) (3)
+ // Therefore result+(eng()-bmin)*mult <
+ // mult+mult*brange by (2), (3) (4)
+ // Therefore result+(eng()-bmin)*mult <
+ // mult*(brange+1) by (4)
result += random::detail::subtract<base_result>()(eng(), bmin) * mult;
+
+ // equivalent to (mult * (brange+1)) == range+1, but avoids overflow.
+ if(mult * range_type(brange) == range - mult + 1) {
+ // The destination range is an integer power of
+ // the generator's range.
+ return(result);
+ }
+
+ // Postcondition: mult <= range
+ //
+ // limit*(brange+1)<=range+1 def. of limit (1)
+ // mult<=limit loop condition (2)
+ // Therefore mult*(brange+1)<=range+1 by (1), (2) (3)
+ // mult*(brange+1)!=range+1 preceding if (4)
+ // Therefore mult*(brange+1)<range+1 by (3), (4) (5)
+ //
+ // Postcondition: result < mult
+ //
+ // See the second postcondition on the change to result.
mult *= range_type(brange)+range_type(1);
}
- if(mult == limit)
- // range+1 is an integer power of brange+1: no rejections required
- return result;
+ // loop postcondition: range/mult < brange+1
+ //
+ // mult > limit loop condition (1)
+ // Suppose range/mult >= brange+1 Assumption (2)
+ // range >= mult*(brange+1) by (2) (3)
+ // range+1 > mult*(brange+1) by (3) (4)
+ // range+1 > (limit+1)*(brange+1) by (1), (4) (5)
+ // (range+1)/(brange+1) > limit+1 by (5) (6)
+ // limit < floor((range+1)/(brange+1)) by (6) (7)
+ // limit==floor((range+1)/(brange+1)) def. of limit (8)
+ // not (2) reductio (9)
+ //
+ // loop postcondition: (range/mult)*mult+(mult-1) >= range
+ //
+ // (range/mult)*mult + range%mult == range identity (1)
+ // range%mult < mult def. of % (2)
+ // (range/mult)*mult+mult > range by (1), (2) (3)
+ // (range/mult)*mult+(mult-1) >= range by (3) (4)
+ //
+ // Note that the maximum value of result at this point is (mult-1),
+ // so after this final step, we generate numbers that can be
+ // at least as large as range. We have to really careful to avoid
+ // overflow in this final addition and in the rejection. Anything
+ // that overflows is larger than range and can thus be rejected.
+
// range/mult < brange+1 -> no endless loop
- result += uniform_int<range_type>(0, range/mult)(eng) * mult;
- if(result <= range)
- return random::detail::add<range_type, result_type>()(result, min_value);
+ range_type result_increment = uniform_int<range_type>(0, range/mult)(eng);
+ if((std::numeric_limits<range_type>::max)() / mult < result_increment) {
+ // The multiplcation would overflow. Reject immediately.
+ continue;
+ }
+ result_increment *= mult;
+ // unsigned integers are guaranteed to wrap on overflow.
+ result += result_increment;
+ if(result < result_increment) {
+ // The addition overflowed. Reject.
+ continue;
+ }
+ if(result > range) {
+ // Too big. Reject.
+ continue;
+ }
+ return random::detail::add<range_type, result_type>()(result, min_value);
}
} else { // brange > range
- if(brange / range > 4 /* quantization_cutoff */ ) {
- // the new range is vastly smaller than the source range,
- // so quantization effects are not relevant
- return boost::uniform_smallint<result_type>(min_value, max_value)(eng);
- } else {
- // use rejection method to handle cases like 0..5 -> 0..4
- for(;;) {
- base_unsigned result =
- random::detail::subtract<base_result>()(eng(), bmin);
- // result and range are non-negative, and result is possibly larger
- // than range, so the cast is safe
- if(result <= static_cast<base_unsigned>(range))
- return random::detail::add<base_unsigned, result_type>()(result, min_value);
+ base_unsigned bucket_size;
+ // it's safe to add 1 to range, as long as we cast it first,
+ // because we know that it is less than brange. However,
+ // we do need to be careful not to cause overflow by adding 1
+ // to brange.
+ if(brange == (std::numeric_limits<base_unsigned>::max)()) {
+ bucket_size = brange / (static_cast<base_unsigned>(range)+1);
+ if(brange % (static_cast<base_unsigned>(range)+1) == static_cast<base_unsigned>(range)) {
+ ++bucket_size;
}
+ } else {
+ bucket_size = (brange+1) / (static_cast<base_unsigned>(range)+1);
+ }
+ for(;;) {
+ base_unsigned result =
+ random::detail::subtract<base_result>()(eng(), bmin);
+ result /= bucket_size;
+ // result and range are non-negative, and result is possibly larger
+ // than range, so the cast is safe
+ if(result <= static_cast<base_unsigned>(range))
+ return random::detail::add<base_unsigned, result_type>()(result, min_value);
}
}
}
Modified: branches/release/boost/random/xor_combine.hpp
==============================================================================
--- branches/release/boost/random/xor_combine.hpp (original)
+++ branches/release/boost/random/xor_combine.hpp 2009-06-13 13:54:06 EDT (Sat, 13 Jun 2009)
@@ -49,9 +49,12 @@
{ }
xor_combine(const base1_type & rng1, const base2_type & rng2)
: _rng1(rng1), _rng2(rng2) { }
+ xor_combine(const result_type & v)
+ : _rng1(v), _rng2(v) { }
template<class It> xor_combine(It& first, It last)
: _rng1(first, last), _rng2( /* advanced by other call */ first, last) { }
void seed() { _rng1.seed(); _rng2.seed(); }
+ void seed(const result_type & v) { _rng1.seed(v); _rng2.seed(v); }
template<class It> void seed(It& first, It last)
{
_rng1.seed(first, last);
Modified: branches/release/libs/random/instantiate.cpp
==============================================================================
--- branches/release/libs/random/instantiate.cpp (original)
+++ branches/release/libs/random/instantiate.cpp 2009-06-13 13:54:06 EDT (Sat, 13 Jun 2009)
@@ -129,12 +129,61 @@
boost::gamma_distribution<RealType>(1));
}
+template<class URNG, class T>
+void test_seed(URNG & urng, const T & t) {
+ URNG urng2(t);
+ BOOST_CHECK(urng == urng2);
+ urng2.seed(t);
+ BOOST_CHECK(urng == urng2);
+}
+
+// rand48 uses non-standard seeding
+template<class T>
+void test_seed(boost::rand48 & urng, const T & t) {
+ boost::rand48 urng2(t);
+ urng2.seed(t);
+}
+
template<class URNG, class ResultType>
-void instantiate_urng(const std::string & s, const URNG &, const ResultType &)
+void instantiate_seed(const URNG &, const ResultType &) {
+ {
+ URNG urng;
+ URNG urng2;
+ urng2.seed();
+ BOOST_CHECK(urng == urng2);
+ }
+ {
+ int value = 127;
+ URNG urng(value);
+
+ // integral types
+ test_seed(urng, static_cast<char>(value));
+ test_seed(urng, static_cast<signed char>(value));
+ test_seed(urng, static_cast<unsigned char>(value));
+ test_seed(urng, static_cast<short>(value));
+ test_seed(urng, static_cast<unsigned short>(value));
+ test_seed(urng, static_cast<int>(value));
+ test_seed(urng, static_cast<unsigned int>(value));
+ test_seed(urng, static_cast<long>(value));
+ test_seed(urng, static_cast<unsigned long>(value));
+#if !defined(BOOST_NO_INT64_T)
+ test_seed(urng, static_cast<boost::int64_t>(value));
+ test_seed(urng, static_cast<boost::uint64_t>(value));
+#endif
+
+ // floating point types
+ test_seed(urng, static_cast<float>(value));
+ test_seed(urng, static_cast<double>(value));
+ test_seed(urng, static_cast<long double>(value));
+ }
+}
+
+template<class URNG, class ResultType>
+void instantiate_urng(const std::string & s, const URNG & u, const ResultType & r)
{
std::cout << "Basic tests for " << s;
URNG urng;
- urng.seed(); // seed() member function
+ instantiate_seed(u, r); // seed() member function
int a[URNG::has_fixed_range ? 5 : 10]; // compile-time constant
(void) a; // avoid "unused" warning
typename URNG::result_type x1 = urng();
@@ -148,6 +197,8 @@
urng();
urng2 = urng; // copy assignment
BOOST_CHECK(urng == urng2);
+ urng2 = URNG(urng2); // copy constructor, not templated constructor
+ BOOST_CHECK(urng == urng2);
#endif // BOOST_MSVC
const std::vector<int> v(9999u, 0x41);
Modified: branches/release/libs/random/random-generators.html
==============================================================================
--- branches/release/libs/random/random-generators.html (original)
+++ branches/release/libs/random/random-generators.html 2009-06-13 13:54:06 EDT (Sat, 13 Jun 2009)
@@ -35,8 +35,8 @@
<li><a href="#mersenne_twister">Class template
<code>random::mersenne_twister</code></a></li>
- <li><a href="#lagged_fibonacci">Class template
- <code>random::lagged_fibonacci</code></a></li>
+ <li><a href="#lagged_fibonacci_01">Class template
+ <code>random::lagged_fibonacci_01</code></a></li>
<li>Performance</li>
</ul>
@@ -351,18 +351,18 @@
typedef random::mersenne_twister< /* ... */ > mt19937;
namespace random {
- template<class FloatType, unsigned int p, unsigned int q>
- class lagged_fibonacci;
+ template<class FloatType, int w, unsigned int p, unsigned int q>
+ class lagged_fibonacci_01;
}
- typedef random::lagged_fibonacci< /* ... */ > lagged_fibonacci607;
- typedef random::lagged_fibonacci< /* ... */ > lagged_fibonacci1279;
- typedef random::lagged_fibonacci< /* ... */ > lagged_fibonacci2281;
- typedef random::lagged_fibonacci< /* ... */ > lagged_fibonacci3217;
- typedef random::lagged_fibonacci< /* ... */ > lagged_fibonacci4423;
- typedef random::lagged_fibonacci< /* ... */ > lagged_fibonacci9689;
- typedef random::lagged_fibonacci< /* ... */ > lagged_fibonacci19937;
- typedef random::lagged_fibonacci< /* ... */ > lagged_fibonacci23209;
- typedef random::lagged_fibonacci< /* ... */ > lagged_fibonacci44497;
+ typedef random::lagged_fibonacci_01< /* ... */ > lagged_fibonacci607;
+ typedef random::lagged_fibonacci_01< /* ... */ > lagged_fibonacci1279;
+ typedef random::lagged_fibonacci_01< /* ... */ > lagged_fibonacci2281;
+ typedef random::lagged_fibonacci_01< /* ... */ > lagged_fibonacci3217;
+ typedef random::lagged_fibonacci_01< /* ... */ > lagged_fibonacci4423;
+ typedef random::lagged_fibonacci_01< /* ... */ > lagged_fibonacci9689;
+ typedef random::lagged_fibonacci_01< /* ... */ > lagged_fibonacci19937;
+ typedef random::lagged_fibonacci_01< /* ... */ > lagged_fibonacci23209;
+ typedef random::lagged_fibonacci_01< /* ... */ > lagged_fibonacci44497;
} // namespace boost
</pre>
@@ -773,7 +773,7 @@
#include <<a href=
"../../boost/random/inversive_congruential.hpp">boost/random/inversive_congruential.hpp</a>>
-template<class IntType, IntType a, IntType b, IntType p>
+template<class IntType, IntType a, IntType b, IntType p, IntType val>
class random::inversive_congruential
{
public:
@@ -789,7 +789,7 @@
IntType operator()();
};
-typedef random::inversive_congruential<int32_t, 9102, 2147483647-36884165, 2147483647> hellekalek1995;
+typedef random::inversive_congruential<int32_t, 9102, 2147483647-36884165, 2147483647, 0> hellekalek1995;
</pre>
<h3>Description</h3>
@@ -812,7 +812,8 @@
<p>The template parameter <code>IntType</code> shall denote a signed
integral type large enough to hold p; a, b, and p are the parameters of the
- generators.</p>
+ generators. The template parameter val is the validation value checked by
+ validation.</p>
<p><em>Note:</em> The implementation currently uses the Euclidian Algorithm
to compute the multiplicative inverse. Therefore, the inversive generators
@@ -849,21 +850,19 @@
#include <<a href=
"../../boost/random/mersenne_twister.hpp">boost/random/mersenne_twister.hpp</a>>
-template<class DataType, int w, int n, int m, int r, DataType a, int u,
-int s, DataType b, int t, DataType c, int l, IntType val>
+template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
+ int s, UIntType b, int t, UIntType c, int l, UIntType val>
class random::mersenne_twister
{
public:
- typedef DataType result_type;
- static const bool has_fixed_range = true;
- static const result_type min_value;
- static const result_type max_value;
+ typedef UIntType result_type;
+ static const bool has_fixed_range = false;
mersenne_twister();
- explicit mersenne_twister(DataType value);
+ explicit mersenne_twister(UIntType value);
template<class Generator> explicit mersenne_twister(Generator & gen);
// compiler-generated copy ctor and assignment operator are fine
void seed();
- void seed(DataType value);
+ void seed(UIntType value);
template<class Generator> void seed(Generator & gen);
result_type operator()();
bool validation(result_type) const;
@@ -918,13 +917,9 @@
<p><strong>Effects:</strong> Constructs a <code>mersenne_twister</code> and
calls <code>seed(gen)</code>.</p>
- <p><em>Note:</em> When using direct-initialization syntax with an lvalue
- (e.g. in the variable definition <code>Gen gen2(gen);</code>), this
- templated constructor will be preferred over the compiler-generated copy
- constructor. For variable definitions which should copy the state of
- another <code>mersenne_twister</code>, use e.g. <code>Gen gen2 =
- gen;</code>, which is copy-initialization syntax and guaranteed to invoke
- the copy constructor.</p>
+ <p><em>Note:</em> The copy constructor will always be preferred over the
+ templated constructor. mersenne_twister takes special steps to guarantee
+ this.</p>
<h3>Seeding</h3>
<pre>
@@ -953,39 +948,35 @@
<p><strong>Complexity:</strong> Exactly <code>n</code> invocations of
<code>gen</code>.</p>
- <p><em>Note:</em> When invoking <code>seed</code> with an lvalue, overload
- resolution chooses the function template unless the type of the argument
- exactly matches <code>result_type</code>. For other integer types, you
- should convert the argument to <code>result_type</code> explicitly.</p>
-
<h3><a name="mt11213b" id="mt11213b"></a><a name="mt19937" id=
"mt19937">Specializations</a></h3>
<p>The specializations <code>mt11213b</code> and <code>mt19937</code> are
from the paper cited above.</p>
- <h2><a name="lagged_fibonacci" id="lagged_fibonacci">Class template
- <code>random::lagged_fibonacci</code></a></h2>
+ <h2><a name="lagged_fibonacci_01" id="lagged_fibonacci_01">Class template
+ <code>random::lagged_fibonacci_01</code></a></h2>
<h3>Synopsis</h3>
<pre>
#include <<a href=
"../../boost/random/lagged_fibonacci.hpp">boost/random/lagged_fibonacci.hpp</a>>
-template<class FloatType, unsigned int p, unsigned int q>
-class lagged_fibonacci
+template<class FloatType, int w, unsigned int p, unsigned int q>
+class lagged_fibonacci_01
{
public:
typedef FloatType result_type;
static const bool has_fixed_range = false;
+ static const int word_size = w;
static const unsigned int long_lag = p;
static const unsigned int short_lag = q;
result_type min() const { return 0.0; }
result_type max() const { return 1.0; }
- lagged_fibonacci();
- explicit lagged_fibonacci(uint32_t value);
+ lagged_fibonacci_01();
+ explicit lagged_fibonacci_01(uint32_t value);
template<class Generator>
- explicit lagged_fibonacci(Generator & gen);
+ explicit lagged_fibonacci_01(Generator & gen);
// compiler-generated copy ctor and assignment operator are fine
void seed(uint32_t value = 331u);
template<class Generator> void seed(Generator & gen);
@@ -993,15 +984,15 @@
bool validation(result_type x) const;
};
-typedef random::lagged_fibonacci<double, 607, 273> lagged_fibonacci607;
-typedef random::lagged_fibonacci<double, 1279, 418> lagged_fibonacci1279;
-typedef random::lagged_fibonacci<double, 2281, 1252> lagged_fibonacci2281;
-typedef random::lagged_fibonacci<double, 3217, 576> lagged_fibonacci3217;
-typedef random::lagged_fibonacci<double, 4423, 2098> lagged_fibonacci4423;
-typedef random::lagged_fibonacci<double, 9689, 5502> lagged_fibonacci9689;
-typedef random::lagged_fibonacci<double, 19937, 9842> lagged_fibonacci19937;
-typedef random::lagged_fibonacci<double, 23209, 13470> lagged_fibonacci23209;
-typedef random::lagged_fibonacci<double, 44497, 21034> lagged_fibonacci44497;
+typedef random::lagged_fibonacci_01<double, 48, 607, 273> lagged_fibonacci607;
+typedef random::lagged_fibonacci_01<double, 48, 1279, 418> lagged_fibonacci1279;
+typedef random::lagged_fibonacci_01<double, 48, 2281, 1252> lagged_fibonacci2281;
+typedef random::lagged_fibonacci_01<double, 48, 3217, 576> lagged_fibonacci3217;
+typedef random::lagged_fibonacci_01<double, 48, 4423, 2098> lagged_fibonacci4423;
+typedef random::lagged_fibonacci_01<double, 48, 9689, 5502> lagged_fibonacci9689;
+typedef random::lagged_fibonacci_01<double, 48, 19937, 9842> lagged_fibonacci19937;
+typedef random::lagged_fibonacci_01<double, 48, 23209, 13470> lagged_fibonacci23209;
+typedef random::lagged_fibonacci_01<double, 48, 44497, 21034> lagged_fibonacci44497;
</pre>
<h3>Description</h3>
@@ -1029,22 +1020,22 @@
<h3>Constructors</h3>
<pre>
-lagged_fibonacci()
+lagged_fibonacci_01()
</pre>
- <p><strong>Effects:</strong> Constructs a <code>lagged_fibonacci</code>
+ <p><strong>Effects:</strong> Constructs a <code>lagged_fibonacci_01</code>
generator and calls <code>seed()</code>.</p>
<pre>
-explicit lagged_fibonacci(uint32_t value)
+explicit lagged_fibonacci_01(uint32_t value)
</pre>
- <p><strong>Effects:</strong> Constructs a <code>lagged_fibonacci</code>
+ <p><strong>Effects:</strong> Constructs a <code>lagged_fibonacci_01</code>
generator and calls <code>seed(value)</code>.</p>
<pre>
-template<class Generator> explicit lagged_fibonacci(Generator & gen)
+template<class Generator> explicit lagged_fibonacci_01(Generator & gen)
</pre>
- <p><strong>Effects:</strong> Constructs a <code>lagged_fibonacci</code>
+ <p><strong>Effects:</strong> Constructs a <code>lagged_fibonacci_01</code>
generator and calls <code>seed(gen)</code>.</p>
<h3>Seeding</h3>
@@ -1065,7 +1056,7 @@
</pre>
<p><strong>Effects:</strong> Sets the state of this
- <code>lagged_fibonacci</code> to the values returned by <code>p</code>
+ <code>lagged_fibonacci_01</code> to the values returned by <code>p</code>
invocations of <code>uniform_01<gen, FloatType></code>.<br>
<strong>Complexity:</strong> Exactly <code>p</code> invocations of
<code>gen</code>.</p>
Modified: branches/release/libs/random/random_test.cpp
==============================================================================
--- branches/release/libs/random/random_test.cpp (original)
+++ branches/release/libs/random/random_test.cpp 2009-06-13 13:54:06 EDT (Sat, 13 Jun 2009)
@@ -64,7 +64,8 @@
for(int k = 0; k < range; k++)
sum += bucket[k];
double avg = static_cast<double>(sum)/range;
- double threshold = 2*avg/std::sqrt(static_cast<double>(iter));
+ double p = 1 / static_cast<double>(range);
+ double threshold = 2*std::sqrt(static_cast<double>(iter)*p*(1-p));
for(int i = 0; i < range; i++) {
if(std::fabs(bucket[i] - avg) > threshold) {
// 95% confidence interval
@@ -100,11 +101,37 @@
// small range => larger range
level_two uint05(uint12, int_gen(-3, 2));
check_uniform_int(uint05, 100000);
+
+ // small range => larger range
+ level_two uint099(uint12, int_gen(0, 99));
+ check_uniform_int(uint099, 100000);
// larger => small range, rejection case
typedef boost::variate_generator<level_two&, int_gen> level_three;
level_three uint1_4(uint05, int_gen(1, 4));
check_uniform_int(uint1_4, 100000);
+
+ typedef boost::uniform_int<boost::uint8_t> int8_gen;
+ typedef boost::variate_generator<Generator&, int8_gen> gen8_t;
+
+ gen8_t gen8_03(gen, int8_gen(0, 3));
+
+ // use the full range of the type, where the destination
+ // range is a power of the source range
+ typedef boost::variate_generator<gen8_t, int8_gen> uniform_uint8;
+ uniform_uint8 uint8_0255(gen8_03, int8_gen(0, 255));
+ check_uniform_int(uint8_0255, 100000);
+
+ // use the full range, but a generator whose range is not
+ // a root of the destination range.
+ gen8_t gen8_02(gen, int8_gen(0, 2));
+ uniform_uint8 uint8_0255_2(gen8_02, int8_gen(0, 255));
+ check_uniform_int(uint8_0255_2, 100000);
+
+ // expand the range to a larger type.
+ typedef boost::variate_generator<gen8_t, int_gen> uniform_uint_from8;
+ uniform_uint_from8 uint0300(gen8_03, int_gen(0, 300));
+ check_uniform_int(uint0300, 100000);
}
#if defined(BOOST_MSVC) && _MSC_VER < 1300
@@ -140,10 +167,13 @@
class ruetti_gen
{
public:
+ ruetti_gen() : state((max)() - 1) {}
typedef boost::uint64_t result_type;
result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return 0; }
result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return std::numeric_limits<result_type>::max BOOST_PREVENT_MACRO_SUBSTITUTION (); }
- result_type operator()() { return (max)()-1; }
+ result_type operator()() { return state--; }
+private:
+ result_type state;
};
void test_overflow_range()