1 /* boost random/linear_feedback_shift.hpp header file
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)
9 * See http://www.boost.org for most recent version including documentation.
11 * $Id: linear_feedback_shift.hpp 71018 2011-04-05 21:27:52Z steven_watanabe $
15 #ifndef BOOST_RANDOM_LINEAR_FEEDBACK_SHIFT_HPP
16 #define BOOST_RANDOM_LINEAR_FEEDBACK_SHIFT_HPP
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>
33 * Instatiations of @c linear_feedback_shift model a
34 * \pseudo_random_number_generator. It was originally
38 * "Random numbers generated by linear recurrence modulo two.",
39 * Tausworthe, R. C.(1965), Mathematics of Computation 19, 201-209.
42 template<class UIntType, int w, int k, int q, int s>
43 class linear_feedback_shift_engine
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);
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(); }
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);
66 /** Constructs a @c linear_feedback_shift_engine, using the default seed. */
67 linear_feedback_shift_engine() { seed(); }
69 /** Constructs a @c linear_feedback_shift_engine, seeding it with s0. */
70 BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(linear_feedback_shift_engine,
74 /** Constructs a @c linear_feedback_shift_engine, seeding it with seq. */
75 BOOST_RANDOM_DETAIL_SEED_SEQ_CONSTRUCTOR(linear_feedback_shift_engine,
80 * Constructs a @c linear_feedback_shift_engine, seeding it with
81 * values from the range [first, last).
83 template<class It> linear_feedback_shift_engine(It& first, It last)
84 { seed(first, last); }
86 /** Seeds a @c linear_feedback_shift_engine with the default seed. */
87 void seed() { seed(default_seed); }
89 /** Seeds a @c linear_feedback_shift_engine with @c s0. */
90 BOOST_RANDOM_DETAIL_ARITHMETIC_SEED(linear_feedback_shift_engine,
93 value = s0 & wordmask();
94 if(value < (1 << (w-k))) {
100 * Seeds a @c linear_feedback_shift_engine with values
101 * produced by @c seq.generate().
103 BOOST_RANDOM_DETAIL_SEED_SEQ_SEED(linear_feedback_shift_engine,
105 { seed(detail::seed_one_int<UIntType, (UIntType(2) << (w - 1))>(seq)); }
108 * Seeds a @c linear_feedback_shift_engine with values
109 * from the range [first, last).
111 template<class It> void seed(It& first, It last)
113 seed(detail::get_one_int<UIntType, (UIntType(2) << (w - 1))>(first, last));
116 /** Returns the next value of the generator. */
117 result_type operator()()
119 const UIntType b = (((value << q) ^ value) & wordmask()) >> (k-s);
120 const UIntType mask = (wordmask() << (w-k)) & wordmask();
121 value = ((value & mask) << s) ^ b;
125 /** Fills a range with random values */
127 void generate(Iter first, Iter last)
128 { detail::generate_from_int(*this, first, last); }
130 /** Advances the state of the generator by @c z. */
131 void discard(boost::uintmax_t z)
133 for(boost::uintmax_t j = 0; j < z; ++j) {
139 * Writes the textual representation of the generator to a @c std::ostream.
141 BOOST_RANDOM_DETAIL_OSTREAM_OPERATOR(os, linear_feedback_shift_engine, x)
148 * Reads the textual representation of the generator from a @c std::istream.
150 BOOST_RANDOM_DETAIL_ISTREAM_OPERATOR(is, linear_feedback_shift_engine, x)
157 * Returns true if the two generators will produce identical
158 * sequences of outputs.
160 BOOST_RANDOM_DETAIL_EQUALITY_OPERATOR(linear_feedback_shift_engine, x, y)
161 { return x.value == y.value; }
164 * Returns true if the two generators will produce different
165 * sequences of outputs.
167 BOOST_RANDOM_DETAIL_INEQUALITY_OPERATOR(linear_feedback_shift_engine)
170 /// \cond show_private
171 static UIntType wordmask() { return boost::low_bits_mask_t<w>::sig_bits; }
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;
192 /// \cond show_deprecated
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>
199 typedef linear_feedback_shift_engine<UIntType, w, k, q, s> base_type;
201 linear_feedback_shift() {}
202 BOOST_RANDOM_DETAIL_SEED_SEQ_CONSTRUCTOR(linear_feedback_shift,
205 BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(linear_feedback_shift,
209 linear_feedback_shift(It& first, It last) : base_type(first, last) {}
214 } // namespace random
217 #endif // BOOST_RANDOM_LINEAR_FEEDBACK_SHIFT_HPP