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. */ |
55 | static result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () |
56 | { return 0; } |
57 | /** Returns the largest value that the generator can produce. */ |
58 | static result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () |
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 | |
161 | result_type S = 0; |
162 | for(std::size_t k = 0; k < n0; ++k) { |
163 | base_unsigned u; |
164 | do { |
165 | u = detail::subtract<base_result_type>()(_base(), (_base.min)()); |
166 | } while(u > base_unsigned(y0 - 1)); |
167 | S = (S << w0) + (u & y0_mask); |
168 | } |
169 | for(std::size_t k = 0; k < (n - n0); ++k) { |
170 | base_unsigned u; |
171 | do { |
172 | u = detail::subtract<base_result_type>()(_base(), (_base.min)()); |
173 | } while(u > base_unsigned(y1 - 1)); |
174 | S = (S << (w0 + 1)) + (u & y1_mask); |
175 | } |
176 | return S; |
177 | } |
178 | |
179 | /** Fills a range with random values */ |
180 | template<class Iter> |
181 | void generate(Iter first, Iter last) |
182 | { detail::generate_from_int(*this, first, last); } |
183 | |
184 | /** Advances the state of the generator by @c z. */ |
185 | void discard(boost::uintmax_t z) |
186 | { |
187 | for(boost::uintmax_t i = 0; i < z; ++i) { |
188 | (*this)(); |
189 | } |
190 | } |
191 | |
192 | const base_type& base() const { return _base; } |
193 | |
194 | /** |
195 | * Writes the textual representation if the generator to a @c std::ostream. |
196 | * The textual representation of the engine is the textual representation |
197 | * of the base engine. |
198 | */ |
199 | BOOST_RANDOM_DETAIL_OSTREAM_OPERATOR(os, independent_bits_engine, r) |
200 | { |
201 | os << r._base; |
202 | return os; |
203 | } |
204 | |
205 | /** |
206 | * Reads the state of an @c independent_bits_engine from a |
207 | * @c std::istream. |
208 | */ |
209 | BOOST_RANDOM_DETAIL_ISTREAM_OPERATOR(is, independent_bits_engine, r) |
210 | { |
211 | is >> r._base; |
212 | return is; |
213 | } |
214 | |
215 | /** |
216 | * Returns: true iff the two @c independent_bits_engines will |
217 | * produce the same sequence of values. |
218 | */ |
219 | BOOST_RANDOM_DETAIL_EQUALITY_OPERATOR(independent_bits_engine, x, y) |
220 | { return x._base == y._base; } |
221 | /** |
222 | * Returns: true iff the two @c independent_bits_engines will |
223 | * produce different sequences of values. |
224 | */ |
225 | BOOST_RANDOM_DETAIL_INEQUALITY_OPERATOR(independent_bits_engine) |
226 | |
227 | private: |
228 | |
229 | /// \cond show_private |
230 | typedef typename boost::random::traits::make_unsigned<base_result_type>::type base_unsigned; |
231 | |
232 | static UIntType max_imp(const boost::true_type&) |
233 | { |
234 | return boost::low_bits_mask_t<w>::sig_bits; |
235 | } |
236 | static UIntType max_imp(const boost::false_type&) |
237 | { |
238 | // We have a multiprecision integer type: |
239 | BOOST_STATIC_ASSERT(std::numeric_limits<UIntType>::is_specialized); |
240 | return w < std::numeric_limits<UIntType>::digits ? UIntType((UIntType(1) << w) - 1) : UIntType((((UIntType(1) << (w - 1)) - 1) << 1) | 1u); |
241 | } |
242 | |
243 | void calc_params( |
244 | std::size_t n, base_unsigned range, |
245 | std::size_t& w0, std::size_t& n0, |
246 | base_unsigned& y0, base_unsigned& y1, |
247 | base_unsigned& y0_mask, base_unsigned& y1_mask) |
248 | { |
249 | BOOST_ASSERT(w >= n); |
250 | w0 = w/n; |
251 | n0 = n - w % n; |
252 | y0_mask = (base_unsigned(2) << (w0 - 1)) - 1; |
253 | y1_mask = (y0_mask << 1) | 1; |
254 | y0 = (range + 1) & ~y0_mask; |
255 | y1 = (range + 1) & ~y1_mask; |
256 | BOOST_ASSERT(y0 != 0 || base_unsigned(range + 1) == 0); |
257 | } |
258 | /// \endcond |
259 | |
260 | Engine _base; |
261 | }; |
262 | |
263 | #ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION |
264 | template<class Engine, std::size_t w, class UIntType> |
265 | const bool independent_bits_engine<Engine, w, UIntType>::has_fixed_range; |
266 | #endif |
267 | |
268 | } // namespace random |
269 | } // namespace boost |
270 | |
271 | #endif // BOOST_RANDOM_INDEPENDENT_BITS_HPP |
272 | |