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
29namespace boost {
30namespace 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 */
42template<class UIntType, int w, int k, int q, int s>
43class linear_feedback_shift_engine
44{
45public:
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
169private:
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
178template<class UIntType, int w, int k, int q, int s>
179const bool linear_feedback_shift_engine<UIntType, w, k, q, s>::has_fixed_range;
180template<class UIntType, int w, int k, int q, int s>
181const int linear_feedback_shift_engine<UIntType, w, k, q, s>::word_size;
182template<class UIntType, int w, int k, int q, int s>
183const int linear_feedback_shift_engine<UIntType, w, k, q, s>::exponent1;
184template<class UIntType, int w, int k, int q, int s>
185const int linear_feedback_shift_engine<UIntType, w, k, q, s>::exponent2;
186template<class UIntType, int w, int k, int q, int s>
187const int linear_feedback_shift_engine<UIntType, w, k, q, s>::step_size;
188template<class UIntType, int w, int k, int q, int s>
189const 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. */
195template<class UIntType, int w, int k, int q, int s, UIntType v = 0>
196class 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;
200public:
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
218