Chris@16: /* boost random/independent_bits.hpp header file
Chris@16:  *
Chris@16:  * Copyright Steven Watanabe 2011
Chris@16:  * Distributed under the Boost Software License, Version 1.0. (See
Chris@16:  * accompanying file LICENSE_1_0.txt or copy at
Chris@16:  * http://www.boost.org/LICENSE_1_0.txt)
Chris@16:  *
Chris@16:  * See http://www.boost.org for most recent version including documentation.
Chris@16:  *
Chris@101:  * $Id$
Chris@16:  *
Chris@16:  */
Chris@16: 
Chris@16: #ifndef BOOST_RANDOM_INDEPENDENT_BITS_HPP
Chris@16: #define BOOST_RANDOM_INDEPENDENT_BITS_HPP
Chris@16: 
Chris@16: #include <istream>
Chris@16: #include <iosfwd>
Chris@16: #include <boost/assert.hpp>
Chris@16: #include <boost/limits.hpp>
Chris@16: #include <boost/config.hpp>
Chris@16: #include <boost/cstdint.hpp>
Chris@16: #include <boost/integer/integer_mask.hpp>
Chris@16: #include <boost/type_traits/make_unsigned.hpp>
Chris@16: #include <boost/random/detail/config.hpp>
Chris@16: #include <boost/random/detail/integer_log2.hpp>
Chris@16: #include <boost/random/detail/operators.hpp>
Chris@16: #include <boost/random/detail/seed.hpp>
Chris@16: #include <boost/random/detail/seed_impl.hpp>
Chris@16: #include <boost/random/detail/signed_unsigned_tools.hpp>
Chris@16: 
Chris@16: namespace boost {
Chris@16: namespace random {
Chris@16: 
Chris@16: /**
Chris@16:  * An instantiation of class template @c independent_bits_engine
Chris@16:  * model a \pseudo_random_number_generator.  It generates random
Chris@16:  * numbers distributed between [0, 2^w) by combining one or
Chris@16:  * more invocations of the base engine.
Chris@16:  *
Chris@16:  * Requires: 0 < w <= std::numeric_limits<UIntType>::digits
Chris@16:  */
Chris@16: template<class Engine, std::size_t w, class UIntType>
Chris@16: class independent_bits_engine
Chris@16: {
Chris@16: public:
Chris@16:     typedef Engine base_type;
Chris@16:     typedef UIntType result_type;
Chris@16: 
Chris@16:     // Required by old Boost.Random concept
Chris@16:     BOOST_STATIC_CONSTANT(bool, has_fixed_range = false);
Chris@16: 
Chris@16:     /** Returns the smallest value that the generator can produce. */
Chris@16:     static result_type min BOOST_PREVENT_MACRO_SUBSTITUTION ()
Chris@16:     { return 0; }
Chris@16:     /** Returns the largest value that the generator can produce. */
Chris@16:     static result_type max BOOST_PREVENT_MACRO_SUBSTITUTION ()
Chris@16:     { return boost::low_bits_mask_t<w>::sig_bits; }
Chris@16: 
Chris@16:     /**
Chris@16:      * Constructs an @c independent_bits_engine using the
Chris@16:      * default constructor of the base generator.
Chris@16:      */
Chris@16:     independent_bits_engine() { }
Chris@16: 
Chris@16:     /**
Chris@16:      * Constructs an @c independent_bits_engine, using seed as
Chris@16:      * the constructor argument for both base generators.
Chris@16:      */
Chris@16:     BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(independent_bits_engine,
Chris@16:         result_type, seed_arg)
Chris@16:     {
Chris@16:         _base.seed(seed_arg);
Chris@16:     }
Chris@16: 
Chris@16:     /**
Chris@16:      * Constructs an @c independent_bits_engine, using seq as
Chris@16:      * the constructor argument for the base generator.
Chris@16:      */
Chris@16:     BOOST_RANDOM_DETAIL_SEED_SEQ_CONSTRUCTOR(independent_bits_engine,
Chris@16:         SeedSeq, seq)
Chris@16:     { _base.seed(seq); }
Chris@16: 
Chris@16:     /** Constructs an @c independent_bits_engine by copying @c base. */
Chris@16:     independent_bits_engine(const base_type& base_arg) : _base(base_arg) {}
Chris@16: 
Chris@16:     /**
Chris@16:      * Contructs an @c independent_bits_engine with
Chris@16:      * values from the range defined by the input iterators first
Chris@16:      * and last.  first will be modified to point to the element
Chris@16:      * after the last one used.
Chris@16:      *
Chris@16:      * Throws: @c std::invalid_argument if the input range is too small.
Chris@16:      *
Chris@16:      * Exception Safety: Basic
Chris@16:      */
Chris@16:     template<class It>
Chris@16:     independent_bits_engine(It& first, It last) : _base(first, last) { }
Chris@16: 
Chris@16:     /**
Chris@16:      * Seeds an @c independent_bits_engine using the default
Chris@16:      * seed of the base generator.
Chris@16:      */
Chris@16:     void seed() { _base.seed(); }
Chris@16: 
Chris@16:     /**
Chris@16:      * Seeds an @c independent_bits_engine, using @c seed as the
Chris@16:      * seed for the base generator.
Chris@16:      */
Chris@16:     BOOST_RANDOM_DETAIL_ARITHMETIC_SEED(independent_bits_engine,
Chris@16:         result_type, seed_arg)
Chris@16:     { _base.seed(seed_arg); }
Chris@16: 
Chris@16:     /**
Chris@16:      * Seeds an @c independent_bits_engine, using @c seq to
Chris@16:      * seed the base generator.
Chris@16:      */
Chris@16:     BOOST_RANDOM_DETAIL_SEED_SEQ_SEED(independent_bits_engine,
Chris@16:         SeedSeq, seq)
Chris@16:     { _base.seed(seq); }
Chris@16: 
Chris@16:     /**
Chris@16:      * Seeds an @c independent_bits_engine with
Chris@16:      * values from the range defined by the input iterators first
Chris@16:      * and last.  first will be modified to point to the element
Chris@16:      * after the last one used.
Chris@16:      *
Chris@16:      * Throws: @c std::invalid_argument if the input range is too small.
Chris@16:      *
Chris@16:      * Exception Safety: Basic
Chris@16:      */
Chris@16:     template<class It> void seed(It& first, It last)
Chris@16:     { _base.seed(first, last); }
Chris@16: 
Chris@16:     /** Returns the next value of the generator. */
Chris@16:     result_type operator()()
Chris@16:     {
Chris@16:         // While it may seem wasteful to recalculate this
Chris@16:         // every time, both msvc and gcc can propagate
Chris@16:         // constants, resolving this at compile time.
Chris@16:         base_unsigned range =
Chris@16:             detail::subtract<base_result>()((_base.max)(), (_base.min)());
Chris@16:         std::size_t m =
Chris@16:             (range == (std::numeric_limits<base_unsigned>::max)()) ?
Chris@16:                 std::numeric_limits<base_unsigned>::digits :
Chris@16:                 detail::integer_log2(range + 1);
Chris@16:         std::size_t n = (w + m - 1) / m;
Chris@16:         std::size_t w0, n0;
Chris@16:         base_unsigned y0, y1;
Chris@16:         base_unsigned y0_mask, y1_mask;
Chris@16:         calc_params(n, range, w0, n0, y0, y1, y0_mask, y1_mask);
Chris@16:         if(base_unsigned(range - y0 + 1) > y0 / n) {
Chris@16:             // increment n and try again.
Chris@16:             ++n;
Chris@16:             calc_params(n, range, w0, n0, y0, y1, y0_mask, y1_mask);
Chris@16:         }
Chris@16: 
Chris@16:         BOOST_ASSERT(n0*w0 + (n - n0)*(w0 + 1) == w);
Chris@16: 
Chris@16:         result_type S = 0;
Chris@16:         for(std::size_t k = 0; k < n0; ++k) {
Chris@16:             base_unsigned u;
Chris@16:             do {
Chris@16:                 u = detail::subtract<base_result>()(_base(), (_base.min)());
Chris@16:             } while(u > base_unsigned(y0 - 1));
Chris@16:             S = (S << w0) + (u & y0_mask);
Chris@16:         }
Chris@16:         for(std::size_t k = 0; k < (n - n0); ++k) {
Chris@16:             base_unsigned u;
Chris@16:             do {
Chris@16:                 u = detail::subtract<base_result>()(_base(), (_base.min)());
Chris@16:             } while(u > base_unsigned(y1 - 1));
Chris@16:             S = (S << (w0 + 1)) + (u & y1_mask);
Chris@16:         }
Chris@16:         return S;
Chris@16:     }
Chris@16:   
Chris@16:     /** Fills a range with random values */
Chris@16:     template<class Iter>
Chris@16:     void generate(Iter first, Iter last)
Chris@16:     { detail::generate_from_int(*this, first, last); }
Chris@16: 
Chris@16:     /** Advances the state of the generator by @c z. */
Chris@16:     void discard(boost::uintmax_t z)
Chris@16:     {
Chris@16:         for(boost::uintmax_t i = 0; i < z; ++i) {
Chris@16:             (*this)();
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     const base_type& base() const { return _base; }
Chris@16: 
Chris@16:     /**
Chris@16:      * Writes the textual representation if the generator to a @c std::ostream.
Chris@16:      * The textual representation of the engine is the textual representation
Chris@16:      * of the base engine.
Chris@16:      */
Chris@16:     BOOST_RANDOM_DETAIL_OSTREAM_OPERATOR(os, independent_bits_engine, r)
Chris@16:     {
Chris@16:         os << r._base;
Chris@16:         return os;
Chris@16:     }
Chris@16: 
Chris@16:     /**
Chris@16:      * Reads the state of an @c independent_bits_engine from a
Chris@16:      * @c std::istream.
Chris@16:      */
Chris@16:     BOOST_RANDOM_DETAIL_ISTREAM_OPERATOR(is, independent_bits_engine, r)
Chris@16:     {
Chris@16:         is >> r._base;
Chris@16:         return is;
Chris@16:     }
Chris@16: 
Chris@16:     /**
Chris@16:      * Returns: true iff the two @c independent_bits_engines will
Chris@16:      * produce the same sequence of values.
Chris@16:      */
Chris@16:     BOOST_RANDOM_DETAIL_EQUALITY_OPERATOR(independent_bits_engine, x, y)
Chris@16:     { return x._base == y._base; }
Chris@16:     /**
Chris@16:      * Returns: true iff the two @c independent_bits_engines will
Chris@16:      * produce different sequences of values.
Chris@16:      */
Chris@16:     BOOST_RANDOM_DETAIL_INEQUALITY_OPERATOR(independent_bits_engine)
Chris@16: 
Chris@16: private:
Chris@16: 
Chris@16:     /// \cond show_private
Chris@16:     typedef typename base_type::result_type base_result;
Chris@16:     typedef typename make_unsigned<base_result>::type base_unsigned;
Chris@16: 
Chris@16:     void calc_params(
Chris@16:         std::size_t n, base_unsigned range,
Chris@16:         std::size_t& w0, std::size_t& n0,
Chris@16:         base_unsigned& y0, base_unsigned& y1,
Chris@16:         base_unsigned& y0_mask, base_unsigned& y1_mask)
Chris@16:     {
Chris@16:         BOOST_ASSERT(w >= n);
Chris@16:         w0 = w/n;
Chris@16:         n0 = n - w % n;
Chris@16:         y0_mask = (base_unsigned(2) << (w0 - 1)) - 1;
Chris@16:         y1_mask = (y0_mask << 1) | 1;
Chris@16:         y0 = (range + 1) & ~y0_mask;
Chris@16:         y1 = (range + 1) & ~y1_mask;
Chris@16:         BOOST_ASSERT(y0 != 0 || base_unsigned(range + 1) == 0);
Chris@16:     }
Chris@16:     /// \endcond
Chris@16: 
Chris@16:     Engine _base;
Chris@16: };
Chris@16: 
Chris@16: #ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION
Chris@16: template<class Engine, std::size_t w, class UIntType>
Chris@16: const bool independent_bits_engine<Engine, w, UIntType>::has_fixed_range;
Chris@16: #endif
Chris@16: 
Chris@16: } // namespace random
Chris@16: } // namespace boost
Chris@16: 
Chris@16: #endif // BOOST_RANDOM_INDEPENDENT_BITS_HPP