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. */ |
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. */ |
128 | IntType a() const { return _min; } |
129 | /** Returns the maximum value. */ |
130 | IntType b() const { return _max; } |
131 | |
132 | |
133 | /** Writes the parameters to a @c std::ostream. */ |
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. */ |
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. */ |
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 | */ |
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 | */ |
169 | explicit uniform_smallint(const param_type& parm) |
170 | : _min(parm.a()), _max(parm.b()) {} |
171 | |
172 | /** Returns the minimum value of the distribution. */ |
173 | result_type a() const { return _min; } |
174 | /** Returns the maximum value of the distribution. */ |
175 | result_type b() const { return _max; } |
176 | /** Returns the minimum value of the distribution. */ |
177 | result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return _min; } |
178 | /** Returns the maximum value of the distribution. */ |
179 | result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return _max; } |
180 | |
181 | /** Returns the parameters of the distribution. */ |
182 | param_type param() const { return param_type(_min, _max); } |
183 | /** Sets the parameters of the distribution. */ |
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 | */ |
194 | void reset() { } |
195 | |
196 | /** Returns a value uniformly distributed in the range [min(), max()]. */ |
197 | template<class Engine> |
198 | 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> |
206 | 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. */ |
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. */ |
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 | */ |
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> |
240 | 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> |
277 | 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 | |