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
37namespace boost {
38namespace 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 */
107template<class IntType = int>
108class uniform_smallint
109{
110public:
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
236private:
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
303using random::uniform_smallint;
304
305} // namespace boost
306
307#endif // BOOST_RANDOM_UNIFORM_SMALLINT_HPP
308