Boost-Commit :

Date view	Thread view	Subject view	Author view

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

Next message: steven_at_[hidden]: "[Boost-commit] svn:boost r53872 - in branches/release: boost/tuple boost/tuple/detail libs/tuple/doc libs/tuple/test"
Previous message: jewillco_at_[hidden]: "[Boost-commit] svn:boost r53870 - trunk/boost/graph"

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()

Next message: steven_at_[hidden]: "[Boost-commit] svn:boost r53872 - in branches/release: boost/tuple boost/tuple/detail libs/tuple/doc libs/tuple/test"
Previous message: jewillco_at_[hidden]: "[Boost-commit] svn:boost r53870 - trunk/boost/graph"

Date view	Thread view	Subject view	Author view

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