[Boost-commit] svn:boost r68813 - in trunk: boost/random libs/random/test

Subject: [Boost-commit] svn:boost r68813 - in trunk: boost/random libs/random/test
From: steven_at_[hidden]
Date: 2011-02-12 13:06:45

Author: steven_watanabe
Date: 2011-02-12 13:06:40 EST (Sat, 12 Feb 2011)
New Revision: 68813
URL: http://svn.boost.org/trac/boost/changeset/68813

Log:
Implement generate_canonical.
Added:
   trunk/boost/random/generate_canonical.hpp   (contents, props changed)
   trunk/libs/random/test/test_generate_canonical.cpp   (contents, props changed)
Text files modified: 
   trunk/boost/random/discard_block.hpp       |    10 ++++++++++                              
   trunk/boost/random/lagged_fibonacci.hpp    |    10 ++++++++++                              
   trunk/boost/random/subtract_with_carry.hpp |    10 ++++++++++                              
   trunk/libs/random/test/Jamfile.v2          |     1 +                                       
   trunk/libs/random/test/concepts.hpp        |    12 ++++++++++++                            
   5 files changed, 43 insertions(+), 0 deletions(-)

Modified: trunk/boost/random/discard_block.hpp
==============================================================================
--- trunk/boost/random/discard_block.hpp	(original)
+++ trunk/boost/random/discard_block.hpp	2011-02-12 13:06:40 EST (Sat, 12 Feb 2011)
@@ -143,6 +143,16 @@
     static result_type max BOOST_PREVENT_MACRO_SUBSTITUTION ()
     { return (base_type::max)(); }
 
+    /**
+     * INTERNAL ONLY
+     * Returns the number of random bits.
+     * This is not part of the standard, and I'm not sure that
+     * it's the best solution, but something like this is needed
+     * to implement generate_canonical.  For now, mark it as
+     * an implementation detail.
+     */
+    static std::size_t precision() { return base_type::precision(); }
+
 #ifndef BOOST_RANDOM_NO_STREAM_OPERATORS
     /** Writes a \discard_block_engine to a @c std::ostream. */
     template<class CharT, class Traits>

Added: trunk/boost/random/generate_canonical.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/random/generate_canonical.hpp	2011-02-12 13:06:40 EST (Sat, 12 Feb 2011)
@@ -0,0 +1,95 @@
+/* boost random/generate_canonical.hpp header file
+ *
+ * Copyright Steven Watanabe 2011
+ * 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)
+ *
+ * See http://www.boost.org for most recent version including documentation.
+ *
+ * $Id$
+ *
+ */
+
+#ifndef BOOST_RANDOM_GENERATE_CANONICAL_HPP
+#define BOOST_RANDOM_GENERATE_CANONICAL_HPP
+
+#include <cassert>
+#include <algorithm>
+#include <boost/config/no_tr1/cmath.hpp>
+#include <boost/limits.hpp>
+#include <boost/type_traits/is_integral.hpp>
+#include <boost/math/special_functions.hpp>
+#include <boost/random/detail/signed_unsigned_tools.hpp>
+
+namespace boost {
+namespace random {
+
+namespace detail {
+
+template<class RealType, std::size_t bits, class URNG>
+RealType generate_canonical_impl(URNG& g, boost::mpl::true_ /*is_integral*/)
+{
+    using std::pow;
+    typedef typename URNG::result_type base_result;
+    std::size_t digits = std::numeric_limits<RealType>::digits;
+    RealType R = RealType(g.max()) - RealType(g.min()) + 1;
+    RealType mult = R;
+    RealType limit = pow(RealType(2), RealType((std::min)(bits, digits)));
+    RealType S = RealType(detail::subtract<base_result>()(g(), (g.min)()));
+    while(mult < limit) {
+        RealType inc = RealType(detail::subtract<base_result>()(g(), (g.min)()));
+        S += inc * mult;
+        mult *= R;
+    }
+    return S / mult;
+}
+
+template<class RealType, std::size_t bits, class URNG>
+RealType generate_canonical_impl(URNG& g, boost::mpl::false_ /*is_integral*/)
+{
+    using std::pow;
+    using std::floor;
+    assert((g.min)() == 0);
+    assert((g.max)() == 1);
+    typedef typename URNG::result_type base_result;
+    std::size_t digits = std::numeric_limits<RealType>::digits;
+    std::size_t engine_bits = g.precision();
+    std::size_t b = (std::min)(bits, digits);
+    std::size_t k = (b  + engine_bits - 1) / engine_bits;
+    RealType R = pow(RealType(2), RealType(engine_bits));
+    RealType mult = R;
+    RealType limit = pow(RealType(2), RealType(b));
+    RealType S = g() - (g.min)();
+    while(mult < limit) {
+        RealType inc(floor((RealType(g()) - RealType((g.min)())) * R));
+        S += inc * mult;
+        mult *= R;
+    }
+    return S / mult;
+}
+
+}
+
+/**
+ * Returns a value uniformly distributed in the range [0, 1)
+ * with at least @c bits random bits.
+ */
+template<class RealType, std::size_t bits, class URNG>
+RealType generate_canonical(URNG& g)
+{
+    RealType result = detail::generate_canonical_impl<RealType, bits>(
+        g, boost::is_integral<typename URNG::result_type>());
+    assert(result >= 0);
+    assert(result <= 1);
+    if(result == 1) {
+        result -= std::numeric_limits<RealType>::epsilon() / 2;
+        assert(result != 1);
+    }
+    return result;
+}
+
+} // namespace random
+} // namespace boost
+
+#endif // BOOST_RANDOM_GENERATE_CANONICAL_HPP

Modified: trunk/boost/random/lagged_fibonacci.hpp
==============================================================================
--- trunk/boost/random/lagged_fibonacci.hpp	(original)
+++ trunk/boost/random/lagged_fibonacci.hpp	2011-02-12 13:06:40 EST (Sat, 12 Feb 2011)
@@ -352,6 +352,16 @@
     /** Returns the upper bound of the generators outputs. */
     static result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () { return result_type(1); }
 
+    /**
+     * INTERNAL ONLY
+     * Returns the number of random bits.
+     * This is not part of the standard, and I'm not sure that
+     * it's the best solution, but something like this is needed
+     * to implement generate_canonical.  For now, mark it as
+     * an implementation detail.
+     */
+    static std::size_t precision() { return w; }
+
     /** Returns the next value of the generator. */
     result_type operator()()
     {

Modified: trunk/boost/random/subtract_with_carry.hpp
==============================================================================
--- trunk/boost/random/subtract_with_carry.hpp	(original)
+++ trunk/boost/random/subtract_with_carry.hpp	2011-02-12 13:06:40 EST (Sat, 12 Feb 2011)
@@ -383,6 +383,16 @@
     static result_type max BOOST_PREVENT_MACRO_SUBSTITUTION ()
     { return result_type(1); }
 
+    /**
+     * INTERNAL ONLY
+     * Returns the number of random bits.
+     * This is not part of the standard, and I'm not sure that
+     * it's the best solution, but something like this is needed
+     * to implement generate_canonical.  For now, mark it as
+     * an implementation detail.
+     */
+    static std::size_t precision() { return w; }
+
     /** Returns the next value of the generator. */
     result_type operator()()
     {

Modified: trunk/libs/random/test/Jamfile.v2
==============================================================================
--- trunk/libs/random/test/Jamfile.v2	(original)
+++ trunk/libs/random/test/Jamfile.v2	2011-02-12 13:06:40 EST (Sat, 12 Feb 2011)
@@ -12,6 +12,7 @@
 
 run random_test.cpp ;
 run test_const_mod.cpp /boost//unit_test_framework ;
+run test_generate_canonical.cpp /boost//unit_test_framework ;
 run ../example/random_demo.cpp ;
 run test_random_device.cpp /boost//random : : : <link>static : test_random_device ;
 run test_random_device.cpp /boost//random : : : <link>shared : test_random_device_dll ;

Modified: trunk/libs/random/test/concepts.hpp
==============================================================================
--- trunk/libs/random/test/concepts.hpp	(original)
+++ trunk/libs/random/test/concepts.hpp	2011-02-12 13:06:40 EST (Sat, 12 Feb 2011)
@@ -14,6 +14,7 @@
 #include <boost/concept/requires.hpp>
 #include <boost/mpl/assert.hpp>
 #include <boost/type_traits/is_arithmetic.hpp>
+#include <boost/type_traits/is_integral.hpp>
 #include <boost/type_traits/is_same.hpp>
 #include <boost/cstdint.hpp>
 #include <boost/static_assert.hpp>
@@ -111,6 +112,8 @@
         same_type(E::min(), result_type());
         same_type(E::max(), result_type());
 
+        check_extra(boost::is_integral<result_type>());
+
         (void)E();
         (void)E(s);
         (void)E(q);
@@ -133,6 +136,15 @@
     seed_seq_archetype<> q;
     result_type s;
     unsigned long long z;
+
+    void check_extra(boost::mpl::true_ /*is_integral*/) {}
+
+    void check_extra(boost::mpl::false_ /*is_integral*/)
+    {
+        // This is an undocumented extension, but we still need
+        // to check for it.
+        same_type(E::precision(), std::size_t(0));
+    }
     
     input_iterator_archetype<boost::uint32_t> sb, se;
 };

Added: trunk/libs/random/test/test_generate_canonical.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/random/test/test_generate_canonical.cpp	2011-02-12 13:06:40 EST (Sat, 12 Feb 2011)
@@ -0,0 +1,103 @@
+/* test_generate_canonical.cpp
+ *
+ * Copyright Steven Watanabe 2011
+ * 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)
+ *
+ * $Id$
+ *
+ */
+
+#include <boost/random/generate_canonical.hpp>
+
+#include <boost/random/linear_congruential.hpp>
+#include <boost/random/mersenne_twister.hpp>
+#include <boost/random/lagged_fibonacci.hpp>
+#include <boost/cstdint.hpp>
+
+#define BOOST_TEST_MAIN
+#include <boost/test/unit_test.hpp>
+
+typedef boost::mpl::vector<
+    boost::random::minstd_rand,
+    boost::random::mt19937,
+    boost::random::lagged_fibonacci607
+> engines;
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(test_float, Engine, engines)
+{
+    Engine eng;
+    Engine expected;
+    for(int i = 0; i < 1000; ++i) {
+        float val = boost::random::generate_canonical<float, 64>(eng);
+        BOOST_CHECK_GE(val, 0);
+        BOOST_CHECK_LT(val, 1);
+    }
+    expected.discard(1000);
+    BOOST_CHECK_EQUAL(eng, expected);
+    for(int i = 0; i < 1000; ++i) {
+        float val = boost::random::generate_canonical<float, 12>(eng);
+        BOOST_CHECK_GE(val, 0);
+        BOOST_CHECK_LT(val, 1);
+    }
+    expected.discard(1000);
+    BOOST_CHECK_EQUAL(eng, expected);
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(test_double, Engine, engines)
+{
+    Engine eng;
+    Engine expected;
+    for(int i = 0; i < 1000; ++i) {
+        double val = boost::random::generate_canonical<double, 64>(eng);
+        BOOST_CHECK_GE(val, 0);
+        BOOST_CHECK_LT(val, 1);
+    }
+    expected.discard(2000);
+    BOOST_CHECK_EQUAL(eng, expected);
+    for(int i = 0; i < 1000; ++i) {
+        double val = boost::random::generate_canonical<double, 12>(eng);
+        BOOST_CHECK_GE(val, 0);
+        BOOST_CHECK_LT(val, 1);
+    }
+    expected.discard(1000);
+    BOOST_CHECK_EQUAL(eng, expected);
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(test_long_double, Engine, engines)
+{
+    Engine eng;
+    Engine expected;
+    for(int i = 0; i < 1000; ++i) {
+        long double val = boost::random::generate_canonical<long double, 60>(eng);
+        BOOST_CHECK_GE(val, 0);
+        BOOST_CHECK_LT(val, 1);
+    }
+    expected.discard(2000);
+    BOOST_CHECK_EQUAL(eng, expected);
+    for(int i = 0; i < 1000; ++i) {
+        long double val = boost::random::generate_canonical<long double, 12>(eng);
+        BOOST_CHECK_GE(val, 0);
+        BOOST_CHECK_LT(val, 1);
+    }
+    expected.discard(1000);
+    BOOST_CHECK_EQUAL(eng, expected);
+}
+
+struct max_engine
+{
+    typedef boost::uint32_t result_type;
+    static result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () { return 0; }
+    static result_type max BOOST_PREVENT_MACRO_SUBSTITUTION ()
+    { return ~boost::uint32_t(0); }
+    result_type operator()() { return max(); }
+};
+
+BOOST_AUTO_TEST_CASE(test_max)
+{
+    max_engine eng;
+    BOOST_CHECK_LT((boost::random::generate_canonical<float, 64>(eng)), 1);
+    BOOST_CHECK_LT((boost::random::generate_canonical<double, 64>(eng)), 1);
+    BOOST_CHECK_LT((boost::random::generate_canonical<long double, 64>(eng)), 1);
+}