]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /* boost random/linear_feedback_shift.hpp header file |
2 | * | |
3 | * Copyright Jens Maurer 2002 | |
4 | * Copyright Steven Watanabe 2011 | |
5 | * Distributed under the Boost Software License, Version 1.0. (See | |
6 | * accompanying file LICENSE_1_0.txt or copy at | |
7 | * http://www.boost.org/LICENSE_1_0.txt) | |
8 | * | |
9 | * See http://www.boost.org for most recent version including documentation. | |
10 | * | |
11 | * $Id$ | |
12 | * | |
13 | */ | |
14 | ||
15 | #ifndef BOOST_RANDOM_LINEAR_FEEDBACK_SHIFT_HPP | |
16 | #define BOOST_RANDOM_LINEAR_FEEDBACK_SHIFT_HPP | |
17 | ||
18 | #include <iosfwd> | |
19 | #include <stdexcept> | |
20 | #include <boost/config.hpp> | |
21 | #include <boost/cstdint.hpp> | |
22 | #include <boost/static_assert.hpp> | |
23 | #include <boost/integer/integer_mask.hpp> | |
24 | #include <boost/random/detail/config.hpp> | |
25 | #include <boost/random/detail/seed.hpp> | |
26 | #include <boost/random/detail/operators.hpp> | |
27 | #include <boost/random/detail/seed_impl.hpp> | |
28 | ||
29 | namespace boost { | |
30 | namespace random { | |
31 | ||
32 | /** | |
33 | * Instatiations of @c linear_feedback_shift model a | |
34 | * \pseudo_random_number_generator. It was originally | |
35 | * proposed in | |
36 | * | |
37 | * @blockquote | |
38 | * "Random numbers generated by linear recurrence modulo two.", | |
39 | * Tausworthe, R. C.(1965), Mathematics of Computation 19, 201-209. | |
40 | * @endblockquote | |
41 | */ | |
42 | template<class UIntType, int w, int k, int q, int s> | |
43 | class linear_feedback_shift_engine | |
44 | { | |
45 | public: | |
46 | typedef UIntType result_type; | |
47 | BOOST_STATIC_CONSTANT(bool, has_fixed_range = false); | |
48 | BOOST_STATIC_CONSTANT(int, word_size = w); | |
49 | BOOST_STATIC_CONSTANT(int, exponent1 = k); | |
50 | BOOST_STATIC_CONSTANT(int, exponent2 = q); | |
51 | BOOST_STATIC_CONSTANT(int, step_size = s); | |
52 | BOOST_STATIC_CONSTANT(UIntType, default_seed = 341); | |
53 | ||
54 | /** Returns the smallest value that the generator can produce. */ | |
55 | static result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () { return 0; } | |
56 | /** Returns the largest value that the generator can produce. */ | |
57 | static result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () | |
58 | { return wordmask(); } | |
59 | ||
60 | BOOST_STATIC_ASSERT(w > 0); | |
61 | BOOST_STATIC_ASSERT(q > 0); | |
62 | BOOST_STATIC_ASSERT(k < w); | |
63 | BOOST_STATIC_ASSERT(0 < 2*q && 2*q < k); | |
64 | BOOST_STATIC_ASSERT(0 < s && s <= k-q); | |
65 | ||
66 | /** Constructs a @c linear_feedback_shift_engine, using the default seed. */ | |
67 | linear_feedback_shift_engine() { seed(); } | |
68 | ||
69 | /** Constructs a @c linear_feedback_shift_engine, seeding it with s0. */ | |
70 | BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(linear_feedback_shift_engine, | |
71 | UIntType, s0) | |
72 | { seed(s0); } | |
73 | ||
74 | /** Constructs a @c linear_feedback_shift_engine, seeding it with seq. */ | |
75 | BOOST_RANDOM_DETAIL_SEED_SEQ_CONSTRUCTOR(linear_feedback_shift_engine, | |
76 | SeedSeq, seq) | |
77 | { seed(seq); } | |
78 | ||
79 | /** | |
80 | * Constructs a @c linear_feedback_shift_engine, seeding it with | |
81 | * values from the range [first, last). | |
82 | */ | |
83 | template<class It> linear_feedback_shift_engine(It& first, It last) | |
84 | { seed(first, last); } | |
85 | ||
86 | /** Seeds a @c linear_feedback_shift_engine with the default seed. */ | |
87 | void seed() { seed(default_seed); } | |
88 | ||
89 | /** Seeds a @c linear_feedback_shift_engine with @c s0. */ | |
90 | BOOST_RANDOM_DETAIL_ARITHMETIC_SEED(linear_feedback_shift_engine, | |
91 | UIntType, s0) | |
92 | { | |
93 | value = s0 & wordmask(); | |
94 | if(value < (1 << (w-k))) { | |
95 | value += 1 << (w-k); | |
96 | } | |
97 | } | |
98 | ||
99 | /** | |
100 | * Seeds a @c linear_feedback_shift_engine with values | |
101 | * produced by @c seq.generate(). | |
102 | */ | |
103 | BOOST_RANDOM_DETAIL_SEED_SEQ_SEED(linear_feedback_shift_engine, | |
104 | SeedSeq, seq) | |
105 | { seed(detail::seed_one_int<UIntType, (UIntType(2) << (w - 1))>(seq)); } | |
106 | ||
107 | /** | |
108 | * Seeds a @c linear_feedback_shift_engine with values | |
109 | * from the range [first, last). | |
110 | */ | |
111 | template<class It> void seed(It& first, It last) | |
112 | { | |
113 | seed(detail::get_one_int<UIntType, (UIntType(2) << (w - 1))>(first, last)); | |
114 | } | |
115 | ||
116 | /** Returns the next value of the generator. */ | |
117 | result_type operator()() | |
118 | { | |
119 | const UIntType b = (((value << q) ^ value) & wordmask()) >> (k-s); | |
120 | const UIntType mask = (wordmask() << (w-k)) & wordmask(); | |
121 | value = ((value & mask) << s) ^ b; | |
122 | return value; | |
123 | } | |
124 | ||
125 | /** Fills a range with random values */ | |
126 | template<class Iter> | |
127 | void generate(Iter first, Iter last) | |
128 | { detail::generate_from_int(*this, first, last); } | |
129 | ||
130 | /** Advances the state of the generator by @c z. */ | |
131 | void discard(boost::uintmax_t z) | |
132 | { | |
133 | for(boost::uintmax_t j = 0; j < z; ++j) { | |
134 | (*this)(); | |
135 | } | |
136 | } | |
137 | ||
138 | /** | |
139 | * Writes the textual representation of the generator to a @c std::ostream. | |
140 | */ | |
141 | BOOST_RANDOM_DETAIL_OSTREAM_OPERATOR(os, linear_feedback_shift_engine, x) | |
142 | { | |
143 | os << x.value; | |
144 | return os; | |
145 | } | |
146 | ||
147 | /** | |
148 | * Reads the textual representation of the generator from a @c std::istream. | |
149 | */ | |
150 | BOOST_RANDOM_DETAIL_ISTREAM_OPERATOR(is, linear_feedback_shift_engine, x) | |
151 | { | |
152 | is >> x.value; | |
153 | return is; | |
154 | } | |
155 | ||
156 | /** | |
157 | * Returns true if the two generators will produce identical | |
158 | * sequences of outputs. | |
159 | */ | |
160 | BOOST_RANDOM_DETAIL_EQUALITY_OPERATOR(linear_feedback_shift_engine, x, y) | |
161 | { return x.value == y.value; } | |
162 | ||
163 | /** | |
164 | * Returns true if the two generators will produce different | |
165 | * sequences of outputs. | |
166 | */ | |
167 | BOOST_RANDOM_DETAIL_INEQUALITY_OPERATOR(linear_feedback_shift_engine) | |
168 | ||
169 | private: | |
170 | /// \cond show_private | |
171 | static UIntType wordmask() { return boost::low_bits_mask_t<w>::sig_bits; } | |
172 | /// \endcond | |
173 | UIntType value; | |
174 | }; | |
175 | ||
176 | #ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION | |
177 | // A definition is required even for integral static constants | |
178 | template<class UIntType, int w, int k, int q, int s> | |
179 | const bool linear_feedback_shift_engine<UIntType, w, k, q, s>::has_fixed_range; | |
180 | template<class UIntType, int w, int k, int q, int s> | |
181 | const int linear_feedback_shift_engine<UIntType, w, k, q, s>::word_size; | |
182 | template<class UIntType, int w, int k, int q, int s> | |
183 | const int linear_feedback_shift_engine<UIntType, w, k, q, s>::exponent1; | |
184 | template<class UIntType, int w, int k, int q, int s> | |
185 | const int linear_feedback_shift_engine<UIntType, w, k, q, s>::exponent2; | |
186 | template<class UIntType, int w, int k, int q, int s> | |
187 | const int linear_feedback_shift_engine<UIntType, w, k, q, s>::step_size; | |
188 | template<class UIntType, int w, int k, int q, int s> | |
189 | const UIntType linear_feedback_shift_engine<UIntType, w, k, q, s>::default_seed; | |
190 | #endif | |
191 | ||
192 | /// \cond show_deprecated | |
193 | ||
194 | /** Provided for backwards compatibility. */ | |
195 | template<class UIntType, int w, int k, int q, int s, UIntType v = 0> | |
196 | class linear_feedback_shift : | |
197 | public linear_feedback_shift_engine<UIntType, w, k, q, s> | |
198 | { | |
199 | typedef linear_feedback_shift_engine<UIntType, w, k, q, s> base_type; | |
200 | public: | |
201 | linear_feedback_shift() {} | |
202 | BOOST_RANDOM_DETAIL_SEED_SEQ_CONSTRUCTOR(linear_feedback_shift, | |
203 | SeedSeq, seq) | |
204 | { seed(seq); } | |
205 | BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(linear_feedback_shift, | |
206 | UIntType, val) | |
207 | { seed(val); } | |
208 | template<class It> | |
209 | linear_feedback_shift(It& first, It last) : base_type(first, last) {} | |
210 | }; | |
211 | ||
212 | /// \endcond | |
213 | ||
214 | } // namespace random | |
215 | } // namespace boost | |
216 | ||
217 | #endif // BOOST_RANDOM_LINEAR_FEEDBACK_SHIFT_HPP |