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