Line data Source code
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 0 : explicit uniform_smallint(IntType min_arg = 0, IntType max_arg = 9)
164 0 : : _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 0 : result_type operator()(Engine& eng) const
199 : {
200 : typedef typename Engine::result_type base_result;
201 0 : 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 0 : 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 0 : range_type range = random::detail::subtract<result_type>()(_max, _min);
256 : base_unsigned base_range =
257 0 : random::detail::subtract<base_result>()((eng.max)(), (eng.min)());
258 : base_unsigned val =
259 0 : random::detail::subtract<base_result>()(eng(), (eng.min)());
260 0 : if(range >= base_range) {
261 0 : return boost::random::detail::add<range_type, result_type>()(
262 0 : 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 0 : mixed_range_type modulus = static_cast<mixed_range_type>(range)+1;
271 0 : return boost::random::detail::add<range_type, result_type>()(
272 0 : 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
|
