random/detail/int_float_pair.hpp

0001 /* boost random/detail/int_float_pair.hpp header file
0002  *
0003  * Copyright Jens Maurer 2000-2001
0004  * Copyright Steven Watanabe 2010-2011
0005  * Distributed under the Boost Software License, Version 1.0. (See
0006  * accompanying file LICENSE_1_0.txt or copy at
0007  * http://www.boost.org/LICENSE_1_0.txt)
0008  *
0009  * See http://www.boost.org for most recent version including documentation.
0010  *
0011  * $Id$
0012  *
0013  */
0014
0015 #ifndef BOOST_RANDOM_DETAIL_INT_FLOAT_PAIR_HPP
0016 #define BOOST_RANDOM_DETAIL_INT_FLOAT_PAIR_HPP
0017
0018 #include <utility>
0019 #include <boost/integer.hpp>
0020 #include <boost/integer/integer_mask.hpp>
0021 #include <boost/type_traits/make_unsigned.hpp>
0022 #include <boost/type_traits/is_integral.hpp>
0023 #include <boost/random/uniform_01.hpp>
0024 #include <boost/random/uniform_int_distribution.hpp>
0025 #include <boost/random/detail/signed_unsigned_tools.hpp>
0026 #include <boost/random/detail/integer_log2.hpp>
0027
0028 namespace boost {
0029 namespace random {
0030 namespace detail {
0031
0032 template<class Engine>
0033 inline typename boost::make_unsigned<typename Engine::result_type>::type
0034 generate_one_digit(Engine& eng, std::size_t bits)
0035 {
0036     typedef typename Engine::result_type base_result;
0037     typedef typename boost::make_unsigned<base_result>::type base_unsigned;
0038
0039     base_unsigned range =
0040         detail::subtract<base_result>()((eng.max)(), (eng.min)());
0041     base_unsigned y0_mask = (base_unsigned(2) << (bits - 1)) - 1;
0042     base_unsigned y0 = (range + 1) & ~y0_mask;
0043     base_unsigned u;
0044     do {
0045         u = detail::subtract<base_result>()(eng(), (eng.min)());
0046     } while(y0 != 0 && u > base_unsigned(y0 - 1));
0047     return u & y0_mask;
0048 }
0049
0050 template<class RealType, std::size_t w, class Engine>
0051 std::pair<RealType, int> generate_int_float_pair(Engine& eng, boost::true_type)
0052 {
0053     typedef typename Engine::result_type base_result;
0054     typedef typename boost::make_unsigned<base_result>::type base_unsigned;
0055
0056     base_unsigned range =
0057         detail::subtract<base_result>()((eng.max)(), (eng.min)());
0058
0059     std::size_t m =
0060         (range == (std::numeric_limits<base_unsigned>::max)()) ?
0061             std::numeric_limits<base_unsigned>::digits :
0062             detail::integer_log2(range + 1);
0063
0064     int bucket = 0;
0065     // process as many full digits as possible into the int part
0066     for(std::size_t i = 0; i < w/m; ++i) {
0067         base_unsigned u = generate_one_digit(eng, m);
0068         bucket = (bucket << m) | u;
0069     }
0070     RealType r;
0071
0072     const std::size_t digits = std::numeric_limits<RealType>::digits;
0073     {
0074         base_unsigned u = generate_one_digit(eng, m);
0075         base_unsigned mask = (base_unsigned(1) << (w%m)) - 1;
0076         bucket = (bucket << (w%m)) | (mask & u);
0077         const RealType mult = RealType(1)/RealType(base_unsigned(1) << (m - w%m));
0078         // zero out unused bits
0079         if (m - w%m > digits) {
0080             u &= ~(base_unsigned(1) << (m - digits));
0081         }
0082         r = RealType(u >> (w%m)) * mult;
0083     }
0084     for(std::size_t i = m - w%m; i + m < digits; i += m) {
0085         base_unsigned u = generate_one_digit(eng, m);
0086         r += u;
0087         r *= RealType(0.5)/RealType(base_unsigned(1) << (m - 1));
0088     }
0089     if (m - w%m < digits)
0090     {
0091         const std::size_t remaining = (digits - m + w%m) % m;
0092         base_unsigned u = generate_one_digit(eng, m);
0093         r += u & ((base_unsigned(2) << (remaining - 1)) - 1);
0094         const RealType mult = RealType(0.5)/RealType(base_unsigned(1) << (remaining - 1));
0095         r *= mult;
0096     }
0097     return std::make_pair(r, bucket);
0098 }
0099
0100 template<class RealType, std::size_t w, class Engine>
0101 inline std::pair<RealType, int> generate_int_float_pair(Engine& eng, boost::false_type)
0102 {
0103     int bucket = uniform_int_distribution<>(0, (1 << w) - 1)(eng);
0104     RealType r = uniform_01<RealType>()(eng);
0105     return std::make_pair(r, bucket);
0106 }
0107
0108 template<class RealType, std::size_t w, class Engine>
0109 inline std::pair<RealType, int> generate_int_float_pair(Engine& eng)
0110 {
0111     typedef typename Engine::result_type base_result;
0112     return generate_int_float_pair<RealType, w>(eng,
0113         boost::is_integral<base_result>());
0114 }
0115
0116 } // namespace detail
0117 } // namespace random
0118 } // namespace boost
0119
0120 #endif // BOOST_RANDOM_DETAIL_INT_FLOAT_PAIR_HPP