ceph/src/boost/boost/random/detail/int_float_pair.hpp

   1 /* boost random/detail/int_float_pair.hpp header file
   2  *
   3  * Copyright Jens Maurer 2000-2001
   4  * Copyright Steven Watanabe 2010-2011
   5  * Distributed under the Boost Software License, Version 1.0. (See
   6  * accompanying file LICENSE_1_0.txt or copy at
   7  * http://www.boost.org/LICENSE_1_0.txt)
   8  *
   9  * See http://www.boost.org for most recent version including documentation.
  10  *
  11  * $Id$
  12  *
  13  */
  14
  15 #ifndef BOOST_RANDOM_DETAIL_INT_FLOAT_PAIR_HPP
  16 #define BOOST_RANDOM_DETAIL_INT_FLOAT_PAIR_HPP
  17
  18 #include <utility>
  19 #include <boost/integer.hpp>
  20 #include <boost/integer/integer_mask.hpp>
  21 #include <boost/type_traits/make_unsigned.hpp>
  22 #include <boost/type_traits/is_integral.hpp>
  23 #include <boost/random/uniform_01.hpp>
  24 #include <boost/random/uniform_int_distribution.hpp>
  25 #include <boost/random/detail/signed_unsigned_tools.hpp>
  26 #include <boost/random/detail/integer_log2.hpp>
  27 #include <boost/mpl/bool.hpp>
  28
  29 namespace boost {
  30 namespace random {
  31 namespace detail {
  32
  33 template<class Engine>
  34 inline typename boost::make_unsigned<typename Engine::result_type>::type
  35 generate_one_digit(Engine& eng, std::size_t bits)
  36 {
  37     typedef typename Engine::result_type base_result;
  38     typedef typename boost::make_unsigned<base_result>::type base_unsigned;
  39
  40     base_unsigned range =
  41         detail::subtract<base_result>()((eng.max)(), (eng.min)());
  42     base_unsigned y0_mask = (base_unsigned(2) << (bits - 1)) - 1;
  43     base_unsigned y0 = (range + 1) & ~y0_mask;
  44     base_unsigned u;
  45     do {
  46         u = detail::subtract<base_result>()(eng(), (eng.min)());
  47     } while(y0 != 0 && u > base_unsigned(y0 - 1));
  48     return u & y0_mask;
  49 }
  50
  51 template<class RealType, std::size_t w, class Engine>
  52 std::pair<RealType, int> generate_int_float_pair(Engine& eng, boost::mpl::true_)
  53 {
  54     typedef typename Engine::result_type base_result;
  55     typedef typename boost::make_unsigned<base_result>::type base_unsigned;
  56
  57     base_unsigned range =
  58         detail::subtract<base_result>()((eng.max)(), (eng.min)());
  59
  60     std::size_t m =
  61         (range == (std::numeric_limits<base_unsigned>::max)()) ?
  62             std::numeric_limits<base_unsigned>::digits :
  63             detail::integer_log2(range + 1);
  64
  65     int bucket = 0;
  66     // process as many full digits as possible into the int part
  67     for(std::size_t i = 0; i < w/m; ++i) {
  68         base_unsigned u = generate_one_digit(eng, m);
  69         bucket = (bucket << m) | u;
  70     }
  71     RealType r;
  72
  73     const std::size_t digits = std::numeric_limits<RealType>::digits;
  74     {
  75         base_unsigned u = generate_one_digit(eng, m);
  76         base_unsigned mask = (base_unsigned(1) << (w%m)) - 1;
  77         bucket = (bucket << (w%m)) | (mask & u);
  78         const RealType mult = RealType(1)/RealType(base_unsigned(1) << (m - w%m));
  79         // zero out unused bits
  80         if (m - w%m > digits) {
  81             u &= ~(base_unsigned(1) << (m - digits));
  82         }
  83         r = RealType(u >> (w%m)) * mult;
  84     }
  85     for(std::size_t i = m - w%m; i + m < digits; ++i) {
  86         base_unsigned u = generate_one_digit(eng, m);
  87         r += u;
  88         r *= RealType(0.5)/RealType(base_unsigned(1) << (m - 1));
  89     }
  90     if (m - w%m < digits)
  91     {
  92         const std::size_t remaining = (digits - m + w%m) % m;
  93         base_unsigned u = generate_one_digit(eng, m);
  94         r += u & ((base_unsigned(2) << (remaining - 1)) - 1);
  95         const RealType mult = RealType(0.5)/RealType(base_unsigned(1) << (remaining - 1));
  96         r *= mult;
  97     }
  98     return std::make_pair(r, bucket);
  99 }
 100
 101 template<class RealType, std::size_t w, class Engine>
 102 inline std::pair<RealType, int> generate_int_float_pair(Engine& eng, boost::mpl::false_)
 103 {
 104     int bucket = uniform_int_distribution<>(0, (1 << w) - 1)(eng);
 105     RealType r = uniform_01<RealType>()(eng);
 106     return std::make_pair(r, bucket);
 107 }
 108
 109 template<class RealType, std::size_t w, class Engine>
 110 inline std::pair<RealType, int> generate_int_float_pair(Engine& eng)
 111 {
 112     typedef typename Engine::result_type base_result;
 113     return generate_int_float_pair<RealType, w>(eng,
 114         boost::is_integral<base_result>());
 115 }
 116
 117 } // namespace detail
 118 } // namespace random
 119 } // namespace boost
 120
 121 #endif // BOOST_RANDOM_DETAIL_INT_FLOAT_PAIR_HPP