EIC code displayed by LXR |
|
|
|
|||
File indexing completed on 2025-01-30 09:59:14
0001 /* boost random/uniform_smallint.hpp header file 0002 * 0003 * Copyright Jens Maurer 2000-2001 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 * Revision history 0013 * 2001-04-08 added min<max assertion (N. Becker) 0014 * 2001-02-18 moved to individual header files 0015 */ 0016 0017 #ifndef BOOST_RANDOM_UNIFORM_SMALLINT_HPP 0018 #define BOOST_RANDOM_UNIFORM_SMALLINT_HPP 0019 0020 #include <istream> 0021 #include <iosfwd> 0022 #include <boost/assert.hpp> 0023 #include <boost/config.hpp> 0024 #include <boost/limits.hpp> 0025 #include <boost/type_traits/is_integral.hpp> 0026 #include <boost/random/detail/config.hpp> 0027 #include <boost/random/detail/operators.hpp> 0028 #include <boost/random/detail/signed_unsigned_tools.hpp> 0029 #include <boost/random/uniform_01.hpp> 0030 #include <boost/detail/workaround.hpp> 0031 0032 #ifdef BOOST_NO_CXX11_EXPLICIT_CONVERSION_OPERATORS 0033 #include <boost/type_traits/conditional.hpp> 0034 #endif 0035 0036 namespace boost { 0037 namespace random { 0038 0039 // uniform integer distribution on a small range [min, max] 0040 0041 /** 0042 * The distribution function uniform_smallint models a \random_distribution. 0043 * On each invocation, it returns a random integer value uniformly distributed 0044 * in the set of integer numbers {min, min+1, min+2, ..., max}. It assumes 0045 * that the desired range (max-min+1) is small compared to the range of the 0046 * underlying source of random numbers and thus makes no attempt to limit 0047 * quantization errors. 0048 * 0049 * Let \f$r_{\mathtt{out}} = (\mbox{max}-\mbox{min}+1)\f$ the desired range of 0050 * integer numbers, and 0051 * let \f$r_{\mathtt{base}}\f$ be the range of the underlying source of random 0052 * numbers. Then, for the uniform distribution, the theoretical probability 0053 * for any number i in the range \f$r_{\mathtt{out}}\f$ will be 0054 * \f$\displaystyle p_{\mathtt{out}}(i) = \frac{1}{r_{\mathtt{out}}}\f$. 0055 * Likewise, assume a uniform distribution on \f$r_{\mathtt{base}}\f$ for 0056 * the underlying source of random numbers, i.e. 0057 * \f$\displaystyle p_{\mathtt{base}}(i) = \frac{1}{r_{\mathtt{base}}}\f$. 0058 * Let \f$p_{\mathtt{out\_s}}(i)\f$ denote the random 0059 * distribution generated by @c uniform_smallint. Then the sum over all 0060 * i in \f$r_{\mathtt{out}}\f$ of 0061 * \f$\displaystyle 0062 * \left(\frac{p_{\mathtt{out\_s}}(i)}{p_{\mathtt{out}}(i)} - 1\right)^2\f$ 0063 * shall not exceed 0064 * \f$\displaystyle \frac{r_{\mathtt{out}}}{r_{\mathtt{base}}^2} 0065 * (r_{\mathtt{base}} \mbox{ mod } r_{\mathtt{out}}) 0066 * (r_{\mathtt{out}} - r_{\mathtt{base}} \mbox{ mod } r_{\mathtt{out}})\f$. 0067 * 0068 * The template parameter IntType shall denote an integer-like value type. 0069 * 0070 * @xmlnote 0071 * The property above is the square sum of the relative differences 0072 * in probabilities between the desired uniform distribution 0073 * \f$p_{\mathtt{out}}(i)\f$ and the generated distribution 0074 * \f$p_{\mathtt{out\_s}}(i)\f$. 0075 * The property can be fulfilled with the calculation 0076 * \f$(\mbox{base\_rng} \mbox{ mod } r_{\mathtt{out}})\f$, as follows: 0077 * Let \f$r = r_{\mathtt{base}} \mbox{ mod } r_{\mathtt{out}}\f$. 0078 * The base distribution on \f$r_{\mathtt{base}}\f$ is folded onto the 0079 * range \f$r_{\mathtt{out}}\f$. The numbers i < r have assigned 0080 * \f$\displaystyle 0081 * \left\lfloor\frac{r_{\mathtt{base}}}{r_{\mathtt{out}}}\right\rfloor+1\f$ 0082 * numbers of the base distribution, the rest has only \f$\displaystyle 0083 * \left\lfloor\frac{r_{\mathtt{base}}}{r_{\mathtt{out}}}\right\rfloor\f$. 0084 * Therefore, 0085 * \f$\displaystyle p_{\mathtt{out\_s}}(i) = 0086 * \left(\left\lfloor\frac{r_{\mathtt{base}}} 0087 * {r_{\mathtt{out}}}\right\rfloor+1\right) / 0088 * r_{\mathtt{base}}\f$ for i < r and \f$\displaystyle p_{\mathtt{out\_s}}(i) = 0089 * \left\lfloor\frac{r_{\mathtt{base}}} 0090 * {r_{\mathtt{out}}}\right\rfloor/r_{\mathtt{base}}\f$ otherwise. 0091 * Substituting this in the 0092 * above sum formula leads to the desired result. 0093 * @endxmlnote 0094 * 0095 * Note: The upper bound for 0096 * \f$(r_{\mathtt{base}} \mbox{ mod } r_{\mathtt{out}}) 0097 * (r_{\mathtt{out}} - r_{\mathtt{base}} \mbox{ mod } r_{\mathtt{out}})\f$ is 0098 * \f$\displaystyle \frac{r_{\mathtt{out}}^2}{4}\f$. Regarding the upper bound 0099 * for the square sum of the relative quantization error of 0100 * \f$\displaystyle \frac{r_\mathtt{out}^3}{4r_{\mathtt{base}}^2}\f$, it 0101 * seems wise to either choose \f$r_{\mathtt{base}}\f$ so that 0102 * \f$r_{\mathtt{base}} > 10r_{\mathtt{out}}^2\f$ or ensure that 0103 * \f$r_{\mathtt{base}}\f$ is 0104 * divisible by \f$r_{\mathtt{out}}\f$. 0105 */ 0106 template<class IntType = int> 0107 class uniform_smallint 0108 { 0109 public: 0110 typedef IntType input_type; 0111 typedef IntType result_type; 0112 0113 class param_type 0114 { 0115 public: 0116 0117 typedef uniform_smallint distribution_type; 0118 0119 /** constructs the parameters of a @c uniform_smallint distribution. */ 0120 param_type(IntType min_arg = 0, IntType max_arg = 9) 0121 : _min(min_arg), _max(max_arg) 0122 { 0123 BOOST_ASSERT(_min <= _max); 0124 } 0125 0126 /** Returns the minimum value. */ 0127 IntType a() const { return _min; } 0128 /** Returns the maximum value. */ 0129 IntType b() const { return _max; } 0130 0131 0132 /** Writes the parameters to a @c std::ostream. */ 0133 BOOST_RANDOM_DETAIL_OSTREAM_OPERATOR(os, param_type, parm) 0134 { 0135 os << parm._min << " " << parm._max; 0136 return os; 0137 } 0138 0139 /** Reads the parameters from a @c std::istream. */ 0140 BOOST_RANDOM_DETAIL_ISTREAM_OPERATOR(is, param_type, parm) 0141 { 0142 is >> parm._min >> std::ws >> parm._max; 0143 return is; 0144 } 0145 0146 /** Returns true if the two sets of parameters are equal. */ 0147 BOOST_RANDOM_DETAIL_EQUALITY_OPERATOR(param_type, lhs, rhs) 0148 { return lhs._min == rhs._min && lhs._max == rhs._max; } 0149 0150 /** Returns true if the two sets of parameters are different. */ 0151 BOOST_RANDOM_DETAIL_INEQUALITY_OPERATOR(param_type) 0152 0153 private: 0154 IntType _min; 0155 IntType _max; 0156 }; 0157 0158 /** 0159 * Constructs a @c uniform_smallint. @c min and @c max are the 0160 * lower and upper bounds of the output range, respectively. 0161 */ 0162 explicit uniform_smallint(IntType min_arg = 0, IntType max_arg = 9) 0163 : _min(min_arg), _max(max_arg) {} 0164 0165 /** 0166 * Constructs a @c uniform_smallint from its parameters. 0167 */ 0168 explicit uniform_smallint(const param_type& parm) 0169 : _min(parm.a()), _max(parm.b()) {} 0170 0171 /** Returns the minimum value of the distribution. */ 0172 result_type a() const { return _min; } 0173 /** Returns the maximum value of the distribution. */ 0174 result_type b() const { return _max; } 0175 /** Returns the minimum value of the distribution. */ 0176 result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return _min; } 0177 /** Returns the maximum value of the distribution. */ 0178 result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return _max; } 0179 0180 /** Returns the parameters of the distribution. */ 0181 param_type param() const { return param_type(_min, _max); } 0182 /** Sets the parameters of the distribution. */ 0183 void param(const param_type& parm) 0184 { 0185 _min = parm.a(); 0186 _max = parm.b(); 0187 } 0188 0189 /** 0190 * Effects: Subsequent uses of the distribution do not depend 0191 * on values produced by any engine prior to invoking reset. 0192 */ 0193 void reset() { } 0194 0195 /** Returns a value uniformly distributed in the range [min(), max()]. */ 0196 template<class Engine> 0197 result_type operator()(Engine& eng) const 0198 { 0199 typedef typename Engine::result_type base_result; 0200 return generate(eng, boost::random::traits::is_integral<base_result>()); 0201 } 0202 0203 /** Returns a value uniformly distributed in the range [param.a(), param.b()]. */ 0204 template<class Engine> 0205 result_type operator()(Engine& eng, const param_type& parm) const 0206 { return uniform_smallint(parm)(eng); } 0207 0208 /** Writes the distribution to a @c std::ostream. */ 0209 BOOST_RANDOM_DETAIL_OSTREAM_OPERATOR(os, uniform_smallint, ud) 0210 { 0211 os << ud._min << " " << ud._max; 0212 return os; 0213 } 0214 0215 /** Reads the distribution from a @c std::istream. */ 0216 BOOST_RANDOM_DETAIL_ISTREAM_OPERATOR(is, uniform_smallint, ud) 0217 { 0218 is >> ud._min >> std::ws >> ud._max; 0219 return is; 0220 } 0221 0222 /** 0223 * Returns true if the two distributions will produce identical 0224 * sequences of values given equal generators. 0225 */ 0226 BOOST_RANDOM_DETAIL_EQUALITY_OPERATOR(uniform_smallint, lhs, rhs) 0227 { return lhs._min == rhs._min && lhs._max == rhs._max; } 0228 0229 /** 0230 * Returns true if the two distributions may produce different 0231 * sequences of values given equal generators. 0232 */ 0233 BOOST_RANDOM_DETAIL_INEQUALITY_OPERATOR(uniform_smallint) 0234 0235 private: 0236 0237 // \cond show_private 0238 template<class Engine> 0239 result_type generate(Engine& eng, boost::true_type) const 0240 { 0241 // equivalent to (eng() - eng.min()) % (_max - _min + 1) + _min, 0242 // but guarantees no overflow. 0243 typedef typename Engine::result_type base_result; 0244 typedef typename boost::random::traits::make_unsigned<base_result>::type base_unsigned; 0245 typedef typename boost::random::traits::make_unsigned_or_unbounded<result_type>::type range_type; 0246 #ifdef BOOST_NO_CXX11_EXPLICIT_CONVERSION_OPERATORS 0247 typedef typename conditional< 0248 std::numeric_limits<range_type>::is_specialized && std::numeric_limits<base_unsigned>::is_specialized 0249 && (std::numeric_limits<range_type>::digits >= std::numeric_limits<base_unsigned>::digits), 0250 range_type, base_unsigned>::type mixed_range_type; 0251 #else 0252 typedef base_unsigned mixed_range_type; 0253 #endif 0254 range_type range = random::detail::subtract<result_type>()(_max, _min); 0255 base_unsigned base_range = 0256 random::detail::subtract<base_result>()((eng.max)(), (eng.min)()); 0257 base_unsigned val = 0258 random::detail::subtract<base_result>()(eng(), (eng.min)()); 0259 if(range >= base_range) { 0260 return boost::random::detail::add<range_type, result_type>()( 0261 static_cast<range_type>(val), _min); 0262 } else { 0263 // This involves mixed arithmetic between the base generators range 0264 // type, and the result_type's range type. mixed_range_type is 0265 // normally the same as base_unsigned which is the most efficient 0266 // option, but requires a narrowing explcit cast if result_type 0267 // is a multiprecision type. If no such casts are available then use 0268 // multiprecision arithmetic throughout instead. 0269 mixed_range_type modulus = static_cast<mixed_range_type>(range)+1; 0270 return boost::random::detail::add<range_type, result_type>()( 0271 static_cast<mixed_range_type>(val) % modulus, _min); 0272 } 0273 } 0274 0275 template<class Engine> 0276 result_type generate(Engine& eng, boost::false_type) const 0277 { 0278 typedef typename Engine::result_type base_result; 0279 typedef typename boost::random::traits::make_unsigned<result_type>::type range_type; 0280 range_type range = random::detail::subtract<result_type>()(_max, _min); 0281 base_result val = boost::uniform_01<base_result>()(eng); 0282 // what is the worst that can possibly happen here? 0283 // base_result may not be able to represent all the values in [0, range] 0284 // exactly. If this happens, it will cause round off error and we 0285 // won't be able to produce all the values in the range. We don't 0286 // care about this because the user has already told us not to by 0287 // using uniform_smallint. However, we do need to be careful 0288 // to clamp the result, or floating point rounding can produce 0289 // an out of range result. 0290 range_type offset = static_cast<range_type>(val * (static_cast<base_result>(range) + 1)); 0291 if(offset > range) return _max; 0292 return boost::random::detail::add<range_type, result_type>()(offset , _min); 0293 } 0294 // \endcond 0295 0296 result_type _min; 0297 result_type _max; 0298 }; 0299 0300 } // namespace random 0301 0302 using random::uniform_smallint; 0303 0304 } // namespace boost 0305 0306 #endif // BOOST_RANDOM_UNIFORM_SMALLINT_HPP
| [ Source navigation ] | [ Diff markup ] | [ Identifier search ] | [ general search ] |
|
This page was automatically generated by the 2.3.7 LXR engine. The LXR team |
|