1 /* boost random/uniform_smallint.hpp header file 2 * 3 * Copyright Jens Maurer 2000-2001 4 * Distributed under the Boost Software License, Version 1.0. (See 5 * accompanying file LICENSE_1_0.txt or copy at 6 * http://www.boost.org/LICENSE_1_0.txt) 7 * 8 * See http://www.boost.org for most recent version including documentation. 9 * 10 * $Id$ 11 * 12 * Revision history 13 * 2001-04-08 added min<max assertion (N. Becker) 14 * 2001-02-18 moved to individual header files 15 */ 16 17 #ifndef BOOST_RANDOM_UNIFORM_SMALLINT_HPP 18 #define BOOST_RANDOM_UNIFORM_SMALLINT_HPP 19 20 #include <istream> 21 #include <iosfwd> 22 #include <boost/assert.hpp> 23 #include <boost/config.hpp> 24 #include <boost/limits.hpp> 25 #include <boost/type_traits/is_integral.hpp> 26 #include <boost/random/detail/config.hpp> 27 #include <boost/random/detail/operators.hpp> 28 #include <boost/random/detail/signed_unsigned_tools.hpp> 29 #include <boost/random/uniform_01.hpp> 30 #include <boost/detail/workaround.hpp> 31 #include <boost/mpl/bool.hpp> 32 33 #ifdef BOOST_NO_CXX11_EXPLICIT_CONVERSION_OPERATORS 34 #include <boost/mpl/if.hpp> 35 #endif 36 37 namespace boost { 38 namespace random { 39 40 // uniform integer distribution on a small range [min, max] 41 42 /** 43 * The distribution function uniform_smallint models a \random_distribution. 44 * On each invocation, it returns a random integer value uniformly distributed 45 * in the set of integer numbers {min, min+1, min+2, ..., max}. It assumes 46 * that the desired range (max-min+1) is small compared to the range of the 47 * underlying source of random numbers and thus makes no attempt to limit 48 * quantization errors. 49 * 50 * Let \f$r_{\mathtt{out}} = (\mbox{max}-\mbox{min}+1)\f$ the desired range of 51 * integer numbers, and 52 * let \f$r_{\mathtt{base}}\f$ be the range of the underlying source of random 53 * numbers. Then, for the uniform distribution, the theoretical probability 54 * for any number i in the range \f$r_{\mathtt{out}}\f$ will be 55 * \f$\displaystyle p_{\mathtt{out}}(i) = \frac{1}{r_{\mathtt{out}}}\f$. 56 * Likewise, assume a uniform distribution on \f$r_{\mathtt{base}}\f$ for 57 * the underlying source of random numbers, i.e. 58 * \f$\displaystyle p_{\mathtt{base}}(i) = \frac{1}{r_{\mathtt{base}}}\f$. 59 * Let \f$p_{\mathtt{out\_s}}(i)\f$ denote the random 60 * distribution generated by @c uniform_smallint. Then the sum over all 61 * i in \f$r_{\mathtt{out}}\f$ of 62 * \f$\displaystyle 63 * \left(\frac{p_{\mathtt{out\_s}}(i)}{p_{\mathtt{out}}(i)} - 1\right)^2\f$ 64 * shall not exceed 65 * \f$\displaystyle \frac{r_{\mathtt{out}}}{r_{\mathtt{base}}^2} 66 * (r_{\mathtt{base}} \mbox{ mod } r_{\mathtt{out}}) 67 * (r_{\mathtt{out}} - r_{\mathtt{base}} \mbox{ mod } r_{\mathtt{out}})\f$. 68 * 69 * The template parameter IntType shall denote an integer-like value type. 70 * 71 * @xmlnote 72 * The property above is the square sum of the relative differences 73 * in probabilities between the desired uniform distribution 74 * \f$p_{\mathtt{out}}(i)\f$ and the generated distribution 75 * \f$p_{\mathtt{out\_s}}(i)\f$. 76 * The property can be fulfilled with the calculation 77 * \f$(\mbox{base\_rng} \mbox{ mod } r_{\mathtt{out}})\f$, as follows: 78 * Let \f$r = r_{\mathtt{base}} \mbox{ mod } r_{\mathtt{out}}\f$. 79 * The base distribution on \f$r_{\mathtt{base}}\f$ is folded onto the 80 * range \f$r_{\mathtt{out}}\f$. The numbers i < r have assigned 81 * \f$\displaystyle 82 * \left\lfloor\frac{r_{\mathtt{base}}}{r_{\mathtt{out}}}\right\rfloor+1\f$ 83 * numbers of the base distribution, the rest has only \f$\displaystyle 84 * \left\lfloor\frac{r_{\mathtt{base}}}{r_{\mathtt{out}}}\right\rfloor\f$. 85 * Therefore, 86 * \f$\displaystyle p_{\mathtt{out\_s}}(i) = 87 * \left(\left\lfloor\frac{r_{\mathtt{base}}} 88 * {r_{\mathtt{out}}}\right\rfloor+1\right) / 89 * r_{\mathtt{base}}\f$ for i < r and \f$\displaystyle p_{\mathtt{out\_s}}(i) = 90 * \left\lfloor\frac{r_{\mathtt{base}}} 91 * {r_{\mathtt{out}}}\right\rfloor/r_{\mathtt{base}}\f$ otherwise. 92 * Substituting this in the 93 * above sum formula leads to the desired result. 94 * @endxmlnote 95 * 96 * Note: The upper bound for 97 * \f$(r_{\mathtt{base}} \mbox{ mod } r_{\mathtt{out}}) 98 * (r_{\mathtt{out}} - r_{\mathtt{base}} \mbox{ mod } r_{\mathtt{out}})\f$ is 99 * \f$\displaystyle \frac{r_{\mathtt{out}}^2}{4}\f$. Regarding the upper bound 100 * for the square sum of the relative quantization error of 101 * \f$\displaystyle \frac{r_\mathtt{out}^3}{4r_{\mathtt{base}}^2}\f$, it 102 * seems wise to either choose \f$r_{\mathtt{base}}\f$ so that 103 * \f$r_{\mathtt{base}} > 10r_{\mathtt{out}}^2\f$ or ensure that 104 * \f$r_{\mathtt{base}}\f$ is 105 * divisible by \f$r_{\mathtt{out}}\f$. 106 */ 107 template<class IntType = int> 108 class uniform_smallint 109 { 110 public: 111 typedef IntType input_type; 112 typedef IntType result_type; 113 114 class param_type 115 { 116 public: 117 118 typedef uniform_smallint distribution_type; 119 120 /** constructs the parameters of a @c uniform_smallint distribution. */ param_type(IntType min_arg=0,IntType max_arg=9)121 param_type(IntType min_arg = 0, IntType max_arg = 9) 122 : _min(min_arg), _max(max_arg) 123 { 124 BOOST_ASSERT(_min <= _max); 125 } 126 127 /** Returns the minimum value. */ a() const128 IntType a() const { return _min; } 129 /** Returns the maximum value. */ b() const130 IntType b() const { return _max; } 131 132 133 /** Writes the parameters to a @c std::ostream. */ BOOST_RANDOM_DETAIL_OSTREAM_OPERATOR(os,param_type,parm)134 BOOST_RANDOM_DETAIL_OSTREAM_OPERATOR(os, param_type, parm) 135 { 136 os << parm._min << " " << parm._max; 137 return os; 138 } 139 140 /** Reads the parameters from a @c std::istream. */ BOOST_RANDOM_DETAIL_ISTREAM_OPERATOR(is,param_type,parm)141 BOOST_RANDOM_DETAIL_ISTREAM_OPERATOR(is, param_type, parm) 142 { 143 is >> parm._min >> std::ws >> parm._max; 144 return is; 145 } 146 147 /** Returns true if the two sets of parameters are equal. */ BOOST_RANDOM_DETAIL_EQUALITY_OPERATOR(param_type,lhs,rhs)148 BOOST_RANDOM_DETAIL_EQUALITY_OPERATOR(param_type, lhs, rhs) 149 { return lhs._min == rhs._min && lhs._max == rhs._max; } 150 151 /** Returns true if the two sets of parameters are different. */ 152 BOOST_RANDOM_DETAIL_INEQUALITY_OPERATOR(param_type) 153 154 private: 155 IntType _min; 156 IntType _max; 157 }; 158 159 /** 160 * Constructs a @c uniform_smallint. @c min and @c max are the 161 * lower and upper bounds of the output range, respectively. 162 */ uniform_smallint(IntType min_arg=0,IntType max_arg=9)163 explicit uniform_smallint(IntType min_arg = 0, IntType max_arg = 9) 164 : _min(min_arg), _max(max_arg) {} 165 166 /** 167 * Constructs a @c uniform_smallint from its parameters. 168 */ uniform_smallint(const param_type & parm)169 explicit uniform_smallint(const param_type& parm) 170 : _min(parm.a()), _max(parm.b()) {} 171 172 /** Returns the minimum value of the distribution. */ a() const173 result_type a() const { return _min; } 174 /** Returns the maximum value of the distribution. */ b() const175 result_type b() const { return _max; } 176 /** Returns the minimum value of the distribution. */ BOOST_PREVENT_MACRO_SUBSTITUTION() const177 result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return _min; } 178 /** Returns the maximum value of the distribution. */ BOOST_PREVENT_MACRO_SUBSTITUTION() const179 result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return _max; } 180 181 /** Returns the parameters of the distribution. */ param() const182 param_type param() const { return param_type(_min, _max); } 183 /** Sets the parameters of the distribution. */ param(const param_type & parm)184 void param(const param_type& parm) 185 { 186 _min = parm.a(); 187 _max = parm.b(); 188 } 189 190 /** 191 * Effects: Subsequent uses of the distribution do not depend 192 * on values produced by any engine prior to invoking reset. 193 */ reset()194 void reset() { } 195 196 /** Returns a value uniformly distributed in the range [min(), max()]. */ 197 template<class Engine> operator ()(Engine & eng) const198 result_type operator()(Engine& eng) const 199 { 200 typedef typename Engine::result_type base_result; 201 return generate(eng, boost::random::traits::is_integral<base_result>()); 202 } 203 204 /** Returns a value uniformly distributed in the range [param.a(), param.b()]. */ 205 template<class Engine> operator ()(Engine & eng,const param_type & parm) const206 result_type operator()(Engine& eng, const param_type& parm) const 207 { return uniform_smallint(parm)(eng); } 208 209 /** Writes the distribution to a @c std::ostream. */ BOOST_RANDOM_DETAIL_OSTREAM_OPERATOR(os,uniform_smallint,ud)210 BOOST_RANDOM_DETAIL_OSTREAM_OPERATOR(os, uniform_smallint, ud) 211 { 212 os << ud._min << " " << ud._max; 213 return os; 214 } 215 216 /** Reads the distribution from a @c std::istream. */ BOOST_RANDOM_DETAIL_ISTREAM_OPERATOR(is,uniform_smallint,ud)217 BOOST_RANDOM_DETAIL_ISTREAM_OPERATOR(is, uniform_smallint, ud) 218 { 219 is >> ud._min >> std::ws >> ud._max; 220 return is; 221 } 222 223 /** 224 * Returns true if the two distributions will produce identical 225 * sequences of values given equal generators. 226 */ BOOST_RANDOM_DETAIL_EQUALITY_OPERATOR(uniform_smallint,lhs,rhs)227 BOOST_RANDOM_DETAIL_EQUALITY_OPERATOR(uniform_smallint, lhs, rhs) 228 { return lhs._min == rhs._min && lhs._max == rhs._max; } 229 230 /** 231 * Returns true if the two distributions may produce different 232 * sequences of values given equal generators. 233 */ 234 BOOST_RANDOM_DETAIL_INEQUALITY_OPERATOR(uniform_smallint) 235 236 private: 237 238 // \cond show_private 239 template<class Engine> generate(Engine & eng,boost::mpl::true_) const240 result_type generate(Engine& eng, boost::mpl::true_) const 241 { 242 // equivalent to (eng() - eng.min()) % (_max - _min + 1) + _min, 243 // but guarantees no overflow. 244 typedef typename Engine::result_type base_result; 245 typedef typename boost::random::traits::make_unsigned<base_result>::type base_unsigned; 246 typedef typename boost::random::traits::make_unsigned_or_unbounded<result_type>::type range_type; 247 #ifdef BOOST_NO_CXX11_EXPLICIT_CONVERSION_OPERATORS 248 typedef typename mpl::if_c< 249 std::numeric_limits<range_type>::is_specialized && std::numeric_limits<base_unsigned>::is_specialized 250 && (std::numeric_limits<range_type>::digits >= std::numeric_limits<base_unsigned>::digits), 251 range_type, base_unsigned>::type mixed_range_type; 252 #else 253 typedef base_unsigned mixed_range_type; 254 #endif 255 range_type range = random::detail::subtract<result_type>()(_max, _min); 256 base_unsigned base_range = 257 random::detail::subtract<base_result>()((eng.max)(), (eng.min)()); 258 base_unsigned val = 259 random::detail::subtract<base_result>()(eng(), (eng.min)()); 260 if(range >= base_range) { 261 return boost::random::detail::add<range_type, result_type>()( 262 static_cast<range_type>(val), _min); 263 } else { 264 // This involves mixed arithmetic between the base generators range 265 // type, and the result_type's range type. mixed_range_type is 266 // normally the same as base_unsigned which is the most efficient 267 // option, but requires a narrowing explcit cast if result_type 268 // is a multiprecision type. If no such casts are available then use 269 // multiprecision arithmetic throughout instead. 270 mixed_range_type modulus = static_cast<mixed_range_type>(range)+1; 271 return boost::random::detail::add<range_type, result_type>()( 272 static_cast<mixed_range_type>(val) % modulus, _min); 273 } 274 } 275 276 template<class Engine> generate(Engine & eng,boost::mpl::false_) const277 result_type generate(Engine& eng, boost::mpl::false_) const 278 { 279 typedef typename Engine::result_type base_result; 280 typedef typename boost::random::traits::make_unsigned<result_type>::type range_type; 281 range_type range = random::detail::subtract<result_type>()(_max, _min); 282 base_result val = boost::uniform_01<base_result>()(eng); 283 // what is the worst that can possibly happen here? 284 // base_result may not be able to represent all the values in [0, range] 285 // exactly. If this happens, it will cause round off error and we 286 // won't be able to produce all the values in the range. We don't 287 // care about this because the user has already told us not to by 288 // using uniform_smallint. However, we do need to be careful 289 // to clamp the result, or floating point rounding can produce 290 // an out of range result. 291 range_type offset = static_cast<range_type>(val * (static_cast<base_result>(range) + 1)); 292 if(offset > range) return _max; 293 return boost::random::detail::add<range_type, result_type>()(offset , _min); 294 } 295 // \endcond 296 297 result_type _min; 298 result_type _max; 299 }; 300 301 } // namespace random 302 303 using random::uniform_smallint; 304 305 } // namespace boost 306 307 #endif // BOOST_RANDOM_UNIFORM_SMALLINT_HPP 308