multiprecision/detail/uniform_int_distribution.hpp

0001 ///////////////////////////////////////////////////////////////
0002 //  Copyright Jens Maurer 2000-2021
0003 //  Copyright Steven Watanabe 2011-2021
0004 //  Copyright John Maddock 2015-2021
0005 //  Copyright Matt Borland 2021
0006 //  Distributed under the Boost Software License, Version 1.0.
0007 //  (See accompanying file LICENSE_1_0.txt or copy at
0008 //  https://www.boost.org/LICENSE_1_0.txt
0009 //
0010 //  This is a C++11 compliant port of Boost.Random's implementation
0011 //  of uniform_int_distribution. See their comments for detailed
0012 //  descriptions
0013
0014 #ifndef BOOST_MP_UNIFORM_INT_DISTRIBUTION_HPP
0015 #define BOOST_MP_UNIFORM_INT_DISTRIBUTION_HPP
0016
0017 #include <limits>
0018 #include <type_traits>
0019 #include <boost/multiprecision/detail/standalone_config.hpp>
0020 #include <boost/multiprecision/detail/assert.hpp>
0021 #include <boost/multiprecision/traits/std_integer_traits.hpp>
0022
0023 namespace boost { namespace multiprecision {
0024
0025 namespace detail {
0026
0027 template <typename T, bool intrinsic>
0028 struct make_unsigned_impl
0029 {
0030     using type = typename boost::multiprecision::detail::make_unsigned<T>::type;
0031 };
0032
0033 template <typename T>
0034 struct make_unsigned_impl<T, false>
0035 {
0036     using type = T;
0037 };
0038
0039 template <typename T>
0040 struct make_unsigned_mp
0041 {
0042     using type = typename make_unsigned_impl<T, boost::multiprecision::detail::is_integral<T>::value>::type;
0043 };
0044
0045 template <typename Engine, typename T>
0046 T generate_uniform_int (Engine& eng, T min_value, T max_value)
0047 {
0048     using range_type = typename boost::multiprecision::detail::make_unsigned_mp<T>::type;
0049     using base_result = typename Engine::result_type;
0050     using base_unsigned = typename boost::multiprecision::detail::make_unsigned_mp<base_result>::type;
0051
0052     const range_type range = max_value - min_value;
0053     const base_result bmin = (eng.min)();
0054     const base_unsigned brange = (eng.max)() - (eng.min)();
0055
0056     if(range == 0)
0057     {
0058         return min_value;
0059     }
0060     else if (brange < range)
0061     {
0062         for(;;)
0063         {
0064             range_type limit;
0065             if(range == (std::numeric_limits<range_type>::max)())
0066             {
0067                 limit = range / (range_type(brange) + 1);
0068                 if(range % (range_type(brange) + 1) == range_type(brange))
0069                 {
0070                     ++limit;
0071                 }
0072             }
0073             else
0074             {
0075                 limit = (range + 1) / (range_type(brange) + 1);
0076             }
0077
0078             range_type result = 0;
0079             range_type mult = 1;
0080
0081             while (mult <= limit)
0082             {
0083                 result += static_cast<range_type>(static_cast<range_type>(eng() - bmin) * mult);
0084
0085                 if(mult * range_type(brange) == range - mult + 1)
0086                 {
0087                     return(result);
0088                 }
0089
0090                 mult *= range_type(brange)+range_type(1);
0091             }
0092
0093             range_type result_increment = generate_uniform_int(eng, range_type(0), range_type(range/mult));
0094
0095             if(std::numeric_limits<range_type>::is_bounded && ((std::numeric_limits<range_type>::max)() / mult < result_increment))
0096             {
0097                 continue;
0098             }
0099
0100             result_increment *= mult;
0101             result += result_increment;
0102
0103             if(result < result_increment)
0104             {
0105                 continue;
0106             }
0107             if(result > range)
0108             {
0109                 continue;
0110             }
0111
0112             return result + min_value;
0113         }
0114     }
0115     else
0116     {
0117         using mixed_range_type =
0118         typename std::conditional<std::numeric_limits<range_type>::is_specialized && std::numeric_limits<base_unsigned>::is_specialized &&
0119                                   (std::numeric_limits<range_type>::digits >= std::numeric_limits<base_unsigned>::digits),
0120                                   range_type, base_unsigned>::type;
0121
0122         mixed_range_type bucket_size;
0123
0124         if(brange == (std::numeric_limits<base_unsigned>::max)())
0125         {
0126             bucket_size = static_cast<mixed_range_type>(brange) / (static_cast<mixed_range_type>(range)+1);
0127             if(static_cast<mixed_range_type>(brange) % (static_cast<mixed_range_type>(range)+1) == static_cast<mixed_range_type>(range))
0128             {
0129                 ++bucket_size;
0130             }
0131         }
0132         else
0133         {
0134             bucket_size = static_cast<mixed_range_type>(brange + 1) / (static_cast<mixed_range_type>(range)+1);
0135         }
0136
0137         for(;;)
0138         {
0139             mixed_range_type result = eng() - bmin;
0140             result /= bucket_size;
0141
0142             if(result <= static_cast<mixed_range_type>(range))
0143             {
0144                 return result + min_value;
0145             }
0146         }
0147     }
0148 }
0149
0150 } // Namespace detail
0151
0152 template <typename Integer = int>
0153 class uniform_int_distribution
0154 {
0155 private:
0156     Integer min_;
0157     Integer max_;
0158
0159 public:
0160     class param_type
0161     {
0162     private:
0163         Integer min_;
0164         Integer max_;
0165
0166     public:
0167         explicit param_type(Integer min_val, Integer max_val) : min_ {min_val}, max_ {max_val}
0168         {
0169             BOOST_MP_ASSERT(min_ <= max_);
0170         }
0171
0172         Integer a() const { return min_; }
0173         Integer b() const { return max_; }
0174     };
0175
0176     explicit uniform_int_distribution(Integer min_arg, Integer max_arg) : min_ {min_arg}, max_ {max_arg}
0177     {
0178         BOOST_MP_ASSERT(min_ <= max_);
0179     }
0180
0181     explicit uniform_int_distribution(const param_type& param_arg) : min_ {param_arg.a()}, max_ {param_arg.b()} {}
0182
0183     Integer min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return min_; }
0184     Integer max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return max_; }
0185
0186     Integer a() const { return min_; }
0187     Integer b() const { return max_; }
0188
0189     param_type param() const { return param_type(min_, max_); }
0190
0191     void param(const param_type& param_arg)
0192     {
0193         min_ = param_arg.a();
0194         max_ = param_arg.b();
0195     }
0196
0197     template <typename Engine>
0198     Integer operator() (Engine& eng) const
0199     {
0200         return detail::generate_uniform_int(eng, min_, max_);
0201     }
0202
0203     template <typename Engine>
0204     Integer operator() (Engine& eng, const param_type& param_arg) const
0205     {
0206         return detail::generate_uniform_int(eng, param_arg.a(), param_arg.b());
0207     }
0208 };
0209
0210 }} // Namespaces
0211
0212 #endif // BOOST_MP_UNIFORM_INT_DISTRIBUTION_HPP