boost/random/independent_bits.hpp

0001 /* boost random/independent_bits.hpp header file
0002  *
0003  * Copyright Steven Watanabe 2011
0004  * Distributed under the Boost Software License, Version 1.0. (See
0005  * accompanying file LICENSE_1_0.txt or copy at
0006  * http://www.boost.org/LICENSE_1_0.txt)
0007  *
0008  * See http://www.boost.org for most recent version including documentation.
0009  *
0010  * $Id$
0011  *
0012  */
0013
0014 #ifndef BOOST_RANDOM_INDEPENDENT_BITS_HPP
0015 #define BOOST_RANDOM_INDEPENDENT_BITS_HPP
0016
0017 #include <istream>
0018 #include <iosfwd>
0019 #include <boost/assert.hpp>
0020 #include <boost/limits.hpp>
0021 #include <boost/config.hpp>
0022 #include <boost/cstdint.hpp>
0023 #include <boost/integer/integer_mask.hpp>
0024 #include <boost/random/traits.hpp>
0025 #include <boost/random/detail/config.hpp>
0026 #include <boost/random/detail/integer_log2.hpp>
0027 #include <boost/random/detail/operators.hpp>
0028 #include <boost/random/detail/seed.hpp>
0029 #include <boost/random/detail/seed_impl.hpp>
0030 #include <boost/random/detail/signed_unsigned_tools.hpp>
0031
0032 namespace boost {
0033 namespace random {
0034
0035 /**
0036  * An instantiation of class template @c independent_bits_engine
0037  * model a \pseudo_random_number_generator.  It generates random
0038  * numbers distributed between [0, 2^w) by combining one or
0039  * more invocations of the base engine.
0040  *
0041  * Requires: 0 < w <= std::numeric_limits<UIntType>::digits
0042  */
0043 template<class Engine, std::size_t w, class UIntType>
0044 class independent_bits_engine
0045 {
0046 public:
0047     typedef Engine base_type;
0048     typedef UIntType result_type;
0049     typedef typename Engine::result_type base_result_type;
0050
0051     // Required by old Boost.Random concept
0052     BOOST_STATIC_CONSTANT(bool, has_fixed_range = false);
0053
0054     /** Returns the smallest value that the generator can produce. */
0055     static BOOST_CONSTEXPR result_type min BOOST_PREVENT_MACRO_SUBSTITUTION ()
0056     { return 0; }
0057     /** Returns the largest value that the generator can produce. */
0058     static BOOST_CONSTEXPR result_type max BOOST_PREVENT_MACRO_SUBSTITUTION ()
0059     { return max_imp(boost::is_integral<UIntType>()); }
0060
0061     /**
0062      * Constructs an @c independent_bits_engine using the
0063      * default constructor of the base generator.
0064      */
0065     independent_bits_engine() { }
0066
0067     /**
0068      * Constructs an @c independent_bits_engine, using seed as
0069      * the constructor argument for both base generators.
0070      */
0071     BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(independent_bits_engine,
0072         base_result_type, seed_arg)
0073     {
0074         _base.seed(seed_arg);
0075     }
0076
0077     /**
0078      * Constructs an @c independent_bits_engine, using seq as
0079      * the constructor argument for the base generator.
0080      */
0081     BOOST_RANDOM_DETAIL_SEED_SEQ_CONSTRUCTOR(independent_bits_engine,
0082         SeedSeq, seq)
0083     { _base.seed(seq); }
0084
0085     /** Constructs an @c independent_bits_engine by copying @c base. */
0086     independent_bits_engine(const base_type& base_arg) : _base(base_arg) {}
0087
0088     /**
0089      * Contructs an @c independent_bits_engine with
0090      * values from the range defined by the input iterators first
0091      * and last.  first will be modified to point to the element
0092      * after the last one used.
0093      *
0094      * Throws: @c std::invalid_argument if the input range is too small.
0095      *
0096      * Exception Safety: Basic
0097      */
0098     template<class It>
0099     independent_bits_engine(It& first, It last) : _base(first, last) { }
0100
0101     /**
0102      * Seeds an @c independent_bits_engine using the default
0103      * seed of the base generator.
0104      */
0105     void seed() { _base.seed(); }
0106
0107     /**
0108      * Seeds an @c independent_bits_engine, using @c seed as the
0109      * seed for the base generator.
0110      */
0111     BOOST_RANDOM_DETAIL_ARITHMETIC_SEED(independent_bits_engine,
0112         base_result_type, seed_arg)
0113     { _base.seed(seed_arg); }
0114
0115     /**
0116      * Seeds an @c independent_bits_engine, using @c seq to
0117      * seed the base generator.
0118      */
0119     BOOST_RANDOM_DETAIL_SEED_SEQ_SEED(independent_bits_engine,
0120         SeedSeq, seq)
0121     { _base.seed(seq); }
0122
0123     /**
0124      * Seeds an @c independent_bits_engine with
0125      * values from the range defined by the input iterators first
0126      * and last.  first will be modified to point to the element
0127      * after the last one used.
0128      *
0129      * Throws: @c std::invalid_argument if the input range is too small.
0130      *
0131      * Exception Safety: Basic
0132      */
0133     template<class It> void seed(It& first, It last)
0134     { _base.seed(first, last); }
0135
0136     /** Returns the next value of the generator. */
0137     result_type operator()()
0138     {
0139         // While it may seem wasteful to recalculate this
0140         // every time, both msvc and gcc can propagate
0141         // constants, resolving this at compile time.
0142         base_unsigned range =
0143             detail::subtract<base_result_type>()((_base.max)(), (_base.min)());
0144         std::size_t m =
0145             (range == (std::numeric_limits<base_unsigned>::max)()) ?
0146                 std::numeric_limits<base_unsigned>::digits :
0147                 detail::integer_log2(range + 1);
0148         std::size_t n = (w + m - 1) / m;
0149         std::size_t w0, n0;
0150         base_unsigned y0, y1;
0151         base_unsigned y0_mask, y1_mask;
0152         calc_params(n, range, w0, n0, y0, y1, y0_mask, y1_mask);
0153         if(base_unsigned(range - y0 + 1) > y0 / n) {
0154             // increment n and try again.
0155             ++n;
0156             calc_params(n, range, w0, n0, y0, y1, y0_mask, y1_mask);
0157         }
0158
0159         BOOST_ASSERT(n0*w0 + (n - n0)*(w0 + 1) == w);
0160
0161         BOOST_ASSERT((n == 1) == (w0 == w));
0162
0163         // special case to avoid undefined behavior from shifting
0164         if(n == 1) {
0165             BOOST_ASSERT(n0 == 1);
0166             base_unsigned u;
0167             do {
0168                 u = detail::subtract<base_result_type>()(_base(), (_base.min)());
0169             } while(u > base_unsigned(y0 - 1));
0170             return u & y0_mask;
0171         }
0172
0173         result_type S = 0;
0174         for(std::size_t k = 0; k < n0; ++k) {
0175             base_unsigned u;
0176             do {
0177                 u = detail::subtract<base_result_type>()(_base(), (_base.min)());
0178             } while(u > base_unsigned(y0 - 1));
0179             S = (S << w0) + (u & y0_mask);
0180         }
0181         for(std::size_t k = 0; k < (n - n0); ++k) {
0182             base_unsigned u;
0183             do {
0184                 u = detail::subtract<base_result_type>()(_base(), (_base.min)());
0185             } while(u > base_unsigned(y1 - 1));
0186             S = (S << (w0 + 1)) + (u & y1_mask);
0187         }
0188         return S;
0189     }
0190
0191     /** Fills a range with random values */
0192     template<class Iter>
0193     void generate(Iter first, Iter last)
0194     { detail::generate_from_int(*this, first, last); }
0195
0196     /** Advances the state of the generator by @c z. */
0197     void discard(boost::uintmax_t z)
0198     {
0199         for(boost::uintmax_t i = 0; i < z; ++i) {
0200             (*this)();
0201         }
0202     }
0203
0204     const base_type& base() const { return _base; }
0205
0206     /**
0207      * Writes the textual representation if the generator to a @c std::ostream.
0208      * The textual representation of the engine is the textual representation
0209      * of the base engine.
0210      */
0211     BOOST_RANDOM_DETAIL_OSTREAM_OPERATOR(os, independent_bits_engine, r)
0212     {
0213         os << r._base;
0214         return os;
0215     }
0216
0217     /**
0218      * Reads the state of an @c independent_bits_engine from a
0219      * @c std::istream.
0220      */
0221     BOOST_RANDOM_DETAIL_ISTREAM_OPERATOR(is, independent_bits_engine, r)
0222     {
0223         is >> r._base;
0224         return is;
0225     }
0226
0227     /**
0228      * Returns: true iff the two @c independent_bits_engines will
0229      * produce the same sequence of values.
0230      */
0231     BOOST_RANDOM_DETAIL_EQUALITY_OPERATOR(independent_bits_engine, x, y)
0232     { return x._base == y._base; }
0233     /**
0234      * Returns: true iff the two @c independent_bits_engines will
0235      * produce different sequences of values.
0236      */
0237     BOOST_RANDOM_DETAIL_INEQUALITY_OPERATOR(independent_bits_engine)
0238
0239 private:
0240
0241     /// \cond show_private
0242     typedef typename boost::random::traits::make_unsigned<base_result_type>::type base_unsigned;
0243
0244     static BOOST_CONSTEXPR UIntType max_imp(const boost::true_type&)
0245     {
0246        return boost::low_bits_mask_t<w>::sig_bits;
0247     }
0248     static UIntType max_imp(const boost::false_type&)
0249     {
0250        // We have a multiprecision integer type:
0251        BOOST_STATIC_ASSERT(std::numeric_limits<UIntType>::is_specialized);
0252        return w < std::numeric_limits<UIntType>::digits ? UIntType((UIntType(1) << w) - 1) : UIntType((((UIntType(1) << (w - 1)) - 1) << 1) | 1u);
0253     }
0254
0255     void calc_params(
0256         std::size_t n, base_unsigned range,
0257         std::size_t& w0, std::size_t& n0,
0258         base_unsigned& y0, base_unsigned& y1,
0259         base_unsigned& y0_mask, base_unsigned& y1_mask)
0260     {
0261         BOOST_ASSERT(w >= n);
0262         w0 = w/n;
0263         n0 = n - w % n;
0264         y0_mask = (base_unsigned(2) << (w0 - 1)) - 1;
0265         y1_mask = (y0_mask << 1) | 1;
0266         y0 = (range + 1) & ~y0_mask;
0267         y1 = (range + 1) & ~y1_mask;
0268         BOOST_ASSERT(y0 != 0 || base_unsigned(range + 1) == 0);
0269     }
0270     /// \endcond
0271
0272     Engine _base;
0273 };
0274
0275 #ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION
0276 template<class Engine, std::size_t w, class UIntType>
0277 const bool independent_bits_engine<Engine, w, UIntType>::has_fixed_range;
0278 #endif
0279
0280 } // namespace random
0281 } // namespace boost
0282
0283 #endif // BOOST_RANDOM_INDEPENDENT_BITS_HPP