]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /* boost random/independent_bits.hpp header file |
2 | * | |
3 | * Copyright Steven Watanabe 2011 | |
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 | */ | |
13 | ||
14 | #ifndef BOOST_RANDOM_INDEPENDENT_BITS_HPP | |
15 | #define BOOST_RANDOM_INDEPENDENT_BITS_HPP | |
16 | ||
17 | #include <istream> | |
18 | #include <iosfwd> | |
19 | #include <boost/assert.hpp> | |
20 | #include <boost/limits.hpp> | |
21 | #include <boost/config.hpp> | |
22 | #include <boost/cstdint.hpp> | |
23 | #include <boost/integer/integer_mask.hpp> | |
24 | #include <boost/random/traits.hpp> | |
25 | #include <boost/random/detail/config.hpp> | |
26 | #include <boost/random/detail/integer_log2.hpp> | |
27 | #include <boost/random/detail/operators.hpp> | |
28 | #include <boost/random/detail/seed.hpp> | |
29 | #include <boost/random/detail/seed_impl.hpp> | |
30 | #include <boost/random/detail/signed_unsigned_tools.hpp> | |
31 | ||
32 | namespace boost { | |
33 | namespace random { | |
34 | ||
35 | /** | |
36 | * An instantiation of class template @c independent_bits_engine | |
37 | * model a \pseudo_random_number_generator. It generates random | |
38 | * numbers distributed between [0, 2^w) by combining one or | |
39 | * more invocations of the base engine. | |
40 | * | |
41 | * Requires: 0 < w <= std::numeric_limits<UIntType>::digits | |
42 | */ | |
43 | template<class Engine, std::size_t w, class UIntType> | |
44 | class independent_bits_engine | |
45 | { | |
46 | public: | |
47 | typedef Engine base_type; | |
48 | typedef UIntType result_type; | |
49 | typedef typename Engine::result_type base_result_type; | |
50 | ||
51 | // Required by old Boost.Random concept | |
52 | BOOST_STATIC_CONSTANT(bool, has_fixed_range = false); | |
53 | ||
54 | /** Returns the smallest value that the generator can produce. */ | |
20effc67 | 55 | static BOOST_CONSTEXPR result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () |
7c673cae FG |
56 | { return 0; } |
57 | /** Returns the largest value that the generator can produce. */ | |
20effc67 | 58 | static BOOST_CONSTEXPR result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () |
7c673cae FG |
59 | { return max_imp(boost::is_integral<UIntType>()); } |
60 | ||
61 | /** | |
62 | * Constructs an @c independent_bits_engine using the | |
63 | * default constructor of the base generator. | |
64 | */ | |
65 | independent_bits_engine() { } | |
66 | ||
67 | /** | |
68 | * Constructs an @c independent_bits_engine, using seed as | |
69 | * the constructor argument for both base generators. | |
70 | */ | |
71 | BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(independent_bits_engine, | |
72 | base_result_type, seed_arg) | |
73 | { | |
74 | _base.seed(seed_arg); | |
75 | } | |
76 | ||
77 | /** | |
78 | * Constructs an @c independent_bits_engine, using seq as | |
79 | * the constructor argument for the base generator. | |
80 | */ | |
81 | BOOST_RANDOM_DETAIL_SEED_SEQ_CONSTRUCTOR(independent_bits_engine, | |
82 | SeedSeq, seq) | |
83 | { _base.seed(seq); } | |
84 | ||
85 | /** Constructs an @c independent_bits_engine by copying @c base. */ | |
86 | independent_bits_engine(const base_type& base_arg) : _base(base_arg) {} | |
87 | ||
88 | /** | |
89 | * Contructs an @c independent_bits_engine with | |
90 | * values from the range defined by the input iterators first | |
91 | * and last. first will be modified to point to the element | |
92 | * after the last one used. | |
93 | * | |
94 | * Throws: @c std::invalid_argument if the input range is too small. | |
95 | * | |
96 | * Exception Safety: Basic | |
97 | */ | |
98 | template<class It> | |
99 | independent_bits_engine(It& first, It last) : _base(first, last) { } | |
100 | ||
101 | /** | |
102 | * Seeds an @c independent_bits_engine using the default | |
103 | * seed of the base generator. | |
104 | */ | |
105 | void seed() { _base.seed(); } | |
106 | ||
107 | /** | |
108 | * Seeds an @c independent_bits_engine, using @c seed as the | |
109 | * seed for the base generator. | |
110 | */ | |
111 | BOOST_RANDOM_DETAIL_ARITHMETIC_SEED(independent_bits_engine, | |
112 | base_result_type, seed_arg) | |
113 | { _base.seed(seed_arg); } | |
114 | ||
115 | /** | |
116 | * Seeds an @c independent_bits_engine, using @c seq to | |
117 | * seed the base generator. | |
118 | */ | |
119 | BOOST_RANDOM_DETAIL_SEED_SEQ_SEED(independent_bits_engine, | |
120 | SeedSeq, seq) | |
121 | { _base.seed(seq); } | |
122 | ||
123 | /** | |
124 | * Seeds an @c independent_bits_engine with | |
125 | * values from the range defined by the input iterators first | |
126 | * and last. first will be modified to point to the element | |
127 | * after the last one used. | |
128 | * | |
129 | * Throws: @c std::invalid_argument if the input range is too small. | |
130 | * | |
131 | * Exception Safety: Basic | |
132 | */ | |
133 | template<class It> void seed(It& first, It last) | |
134 | { _base.seed(first, last); } | |
135 | ||
136 | /** Returns the next value of the generator. */ | |
137 | result_type operator()() | |
138 | { | |
139 | // While it may seem wasteful to recalculate this | |
140 | // every time, both msvc and gcc can propagate | |
141 | // constants, resolving this at compile time. | |
142 | base_unsigned range = | |
143 | detail::subtract<base_result_type>()((_base.max)(), (_base.min)()); | |
144 | std::size_t m = | |
145 | (range == (std::numeric_limits<base_unsigned>::max)()) ? | |
146 | std::numeric_limits<base_unsigned>::digits : | |
147 | detail::integer_log2(range + 1); | |
148 | std::size_t n = (w + m - 1) / m; | |
149 | std::size_t w0, n0; | |
150 | base_unsigned y0, y1; | |
151 | base_unsigned y0_mask, y1_mask; | |
152 | calc_params(n, range, w0, n0, y0, y1, y0_mask, y1_mask); | |
153 | if(base_unsigned(range - y0 + 1) > y0 / n) { | |
154 | // increment n and try again. | |
155 | ++n; | |
156 | calc_params(n, range, w0, n0, y0, y1, y0_mask, y1_mask); | |
157 | } | |
158 | ||
159 | BOOST_ASSERT(n0*w0 + (n - n0)*(w0 + 1) == w); | |
160 | ||
11fdf7f2 TL |
161 | BOOST_ASSERT((n == 1) == (w0 == w)); |
162 | ||
163 | // special case to avoid undefined behavior from shifting | |
164 | if(n == 1) { | |
165 | BOOST_ASSERT(n0 == 1); | |
166 | base_unsigned u; | |
167 | do { | |
168 | u = detail::subtract<base_result_type>()(_base(), (_base.min)()); | |
169 | } while(u > base_unsigned(y0 - 1)); | |
170 | return u & y0_mask; | |
171 | } | |
172 | ||
7c673cae FG |
173 | result_type S = 0; |
174 | for(std::size_t k = 0; k < n0; ++k) { | |
175 | base_unsigned u; | |
176 | do { | |
177 | u = detail::subtract<base_result_type>()(_base(), (_base.min)()); | |
178 | } while(u > base_unsigned(y0 - 1)); | |
179 | S = (S << w0) + (u & y0_mask); | |
180 | } | |
181 | for(std::size_t k = 0; k < (n - n0); ++k) { | |
182 | base_unsigned u; | |
183 | do { | |
184 | u = detail::subtract<base_result_type>()(_base(), (_base.min)()); | |
185 | } while(u > base_unsigned(y1 - 1)); | |
186 | S = (S << (w0 + 1)) + (u & y1_mask); | |
187 | } | |
188 | return S; | |
189 | } | |
190 | ||
191 | /** Fills a range with random values */ | |
192 | template<class Iter> | |
193 | void generate(Iter first, Iter last) | |
194 | { detail::generate_from_int(*this, first, last); } | |
195 | ||
196 | /** Advances the state of the generator by @c z. */ | |
197 | void discard(boost::uintmax_t z) | |
198 | { | |
199 | for(boost::uintmax_t i = 0; i < z; ++i) { | |
200 | (*this)(); | |
201 | } | |
202 | } | |
203 | ||
204 | const base_type& base() const { return _base; } | |
205 | ||
206 | /** | |
207 | * Writes the textual representation if the generator to a @c std::ostream. | |
208 | * The textual representation of the engine is the textual representation | |
209 | * of the base engine. | |
210 | */ | |
211 | BOOST_RANDOM_DETAIL_OSTREAM_OPERATOR(os, independent_bits_engine, r) | |
212 | { | |
213 | os << r._base; | |
214 | return os; | |
215 | } | |
216 | ||
217 | /** | |
218 | * Reads the state of an @c independent_bits_engine from a | |
219 | * @c std::istream. | |
220 | */ | |
221 | BOOST_RANDOM_DETAIL_ISTREAM_OPERATOR(is, independent_bits_engine, r) | |
222 | { | |
223 | is >> r._base; | |
224 | return is; | |
225 | } | |
226 | ||
227 | /** | |
228 | * Returns: true iff the two @c independent_bits_engines will | |
229 | * produce the same sequence of values. | |
230 | */ | |
231 | BOOST_RANDOM_DETAIL_EQUALITY_OPERATOR(independent_bits_engine, x, y) | |
232 | { return x._base == y._base; } | |
233 | /** | |
234 | * Returns: true iff the two @c independent_bits_engines will | |
235 | * produce different sequences of values. | |
236 | */ | |
237 | BOOST_RANDOM_DETAIL_INEQUALITY_OPERATOR(independent_bits_engine) | |
238 | ||
239 | private: | |
240 | ||
241 | /// \cond show_private | |
242 | typedef typename boost::random::traits::make_unsigned<base_result_type>::type base_unsigned; | |
243 | ||
20effc67 | 244 | static BOOST_CONSTEXPR UIntType max_imp(const boost::true_type&) |
7c673cae FG |
245 | { |
246 | return boost::low_bits_mask_t<w>::sig_bits; | |
247 | } | |
248 | static UIntType max_imp(const boost::false_type&) | |
249 | { | |
250 | // We have a multiprecision integer type: | |
251 | BOOST_STATIC_ASSERT(std::numeric_limits<UIntType>::is_specialized); | |
252 | return w < std::numeric_limits<UIntType>::digits ? UIntType((UIntType(1) << w) - 1) : UIntType((((UIntType(1) << (w - 1)) - 1) << 1) | 1u); | |
253 | } | |
254 | ||
255 | void calc_params( | |
256 | std::size_t n, base_unsigned range, | |
257 | std::size_t& w0, std::size_t& n0, | |
258 | base_unsigned& y0, base_unsigned& y1, | |
259 | base_unsigned& y0_mask, base_unsigned& y1_mask) | |
260 | { | |
261 | BOOST_ASSERT(w >= n); | |
262 | w0 = w/n; | |
263 | n0 = n - w % n; | |
264 | y0_mask = (base_unsigned(2) << (w0 - 1)) - 1; | |
265 | y1_mask = (y0_mask << 1) | 1; | |
266 | y0 = (range + 1) & ~y0_mask; | |
267 | y1 = (range + 1) & ~y1_mask; | |
268 | BOOST_ASSERT(y0 != 0 || base_unsigned(range + 1) == 0); | |
269 | } | |
270 | /// \endcond | |
271 | ||
272 | Engine _base; | |
273 | }; | |
274 | ||
275 | #ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION | |
276 | template<class Engine, std::size_t w, class UIntType> | |
277 | const bool independent_bits_engine<Engine, w, UIntType>::has_fixed_range; | |
278 | #endif | |
279 | ||
280 | } // namespace random | |
281 | } // namespace boost | |
282 | ||
283 | #endif // BOOST_RANDOM_INDEPENDENT_BITS_HPP |