1/* boost random/lagged_fibonacci.hpp header file
2 *
3 * Copyright Jens Maurer 2000-2001
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 * Revision history
13 * 2013-10-14 fixed some warnings with Wshadow (mgaunard)
14 * 2001-02-18 moved to individual header files
15 */
16
17#ifndef BOOST_RANDOM_LAGGED_FIBONACCI_HPP
18#define BOOST_RANDOM_LAGGED_FIBONACCI_HPP
19
20#include <istream>
21#include <iosfwd>
22#include <algorithm> // std::max
23#include <iterator>
24#include <boost/config/no_tr1/cmath.hpp> // std::pow
25#include <boost/config.hpp>
26#include <boost/limits.hpp>
27#include <boost/cstdint.hpp>
28#include <boost/integer/integer_mask.hpp>
29#include <boost/random/linear_congruential.hpp>
30#include <boost/random/uniform_01.hpp>
31#include <boost/random/detail/config.hpp>
32#include <boost/random/detail/seed.hpp>
33#include <boost/random/detail/operators.hpp>
34#include <boost/random/detail/generator_seed_seq.hpp>
35
36namespace boost {
37namespace random {
38
39/**
40 * Instantiations of class template \lagged_fibonacci_engine model a
41 * \pseudo_random_number_generator. It uses a lagged Fibonacci
42 * algorithm with two lags @c p and @c q:
43 * x(i) = x(i-p) + x(i-q) (mod 2<sup>w</sup>) with p > q.
44 */
45template<class UIntType, int w, unsigned int p, unsigned int q>
46class lagged_fibonacci_engine
47{
48public:
49 typedef UIntType result_type;
50 BOOST_STATIC_CONSTANT(bool, has_fixed_range = false);
51 BOOST_STATIC_CONSTANT(int, word_size = w);
52 BOOST_STATIC_CONSTANT(unsigned int, long_lag = p);
53 BOOST_STATIC_CONSTANT(unsigned int, short_lag = q);
54
55 BOOST_STATIC_CONSTANT(UIntType, default_seed = 331u);
56
57 /** Returns the smallest value that the generator can produce. */
58 static result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () { return 0; }
59 /** Returns the largest value that the generator can produce. */
60 static result_type max BOOST_PREVENT_MACRO_SUBSTITUTION ()
61 { return low_bits_mask_t<w>::sig_bits; }
62
63 /** Creates a new @c lagged_fibonacci_engine and calls @c seed(). */
64 lagged_fibonacci_engine() { seed(); }
65
66 /** Creates a new @c lagged_fibonacci_engine and calls @c seed(value). */
67 BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(lagged_fibonacci_engine,
68 UIntType, value)
69 { seed(value); }
70
71 /** Creates a new @c lagged_fibonacci_engine and calls @c seed(seq). */
72 BOOST_RANDOM_DETAIL_SEED_SEQ_CONSTRUCTOR(lagged_fibonacci_engine,
73 SeedSeq, seq)
74 { seed(seq); }
75
76 /**
77 * Creates a new @c lagged_fibonacci_engine and calls @c seed(first, last).
78 */
79 template<class It> lagged_fibonacci_engine(It& first, It last)
80 { seed(first, last); }
81
82 // compiler-generated copy ctor and assignment operator are fine
83
84 /** Calls @c seed(default_seed). */
85 void seed() { seed(default_seed); }
86
87 /**
88 * Sets the state of the generator to values produced by
89 * a \minstd_rand0 generator.
90 */
91 BOOST_RANDOM_DETAIL_ARITHMETIC_SEED(lagged_fibonacci_engine,
92 UIntType, value)
93 {
94 minstd_rand0 intgen(static_cast<boost::uint32_t>(value));
95 detail::generator_seed_seq<minstd_rand0> gen(intgen);
96 seed(gen);
97 }
98
99 /**
100 * Sets the state of the generator using values produced by seq.
101 */
102 BOOST_RANDOM_DETAIL_SEED_SEQ_SEED(lagged_fibonacci_engine, SeedSeq, seq)
103 {
104 detail::seed_array_int<w>(seq, x);
105 i = long_lag;
106 }
107
108 /**
109 * Sets the state of the generator to values from the iterator
110 * range [first, last). If there are not enough elements in the
111 * range [first, last) throws @c std::invalid_argument.
112 */
113 template<class It>
114 void seed(It& first, It last)
115 {
116 detail::fill_array_int<w>(first, last, x);
117 i = long_lag;
118 }
119
120 /** Returns the next value of the generator. */
121 result_type operator()()
122 {
123 if(i >= long_lag)
124 fill();
125 return x[i++];
126 }
127
128 /** Fills a range with random values */
129 template<class Iter>
130 void generate(Iter first, Iter last)
131 { detail::generate_from_int(*this, first, last); }
132
133 /** Advances the state of the generator by @c z. */
134 void discard(boost::uintmax_t z)
135 {
136 for(boost::uintmax_t j = 0; j < z; ++j) {
137 (*this)();
138 }
139 }
140
141 /**
142 * Writes the textual representation of the generator to a @c std::ostream.
143 */
144 BOOST_RANDOM_DETAIL_OSTREAM_OPERATOR(os, lagged_fibonacci_engine, f)
145 {
146 os << f.i;
147 for(unsigned int j = 0; j < f.long_lag; ++j)
148 os << ' ' << f.x[j];
149 return os;
150 }
151
152 /**
153 * Reads the textual representation of the generator from a @c std::istream.
154 */
155 BOOST_RANDOM_DETAIL_ISTREAM_OPERATOR(is, lagged_fibonacci_engine, f)
156 {
157 is >> f.i >> std::ws;
158 for(unsigned int j = 0; j < f.long_lag; ++j)
159 is >> f.x[j] >> std::ws;
160 return is;
161 }
162
163 /**
164 * Returns true if the two generators will produce identical
165 * sequences of outputs.
166 */
167 BOOST_RANDOM_DETAIL_EQUALITY_OPERATOR(lagged_fibonacci_engine, x_, y_)
168 { return x_.i == y_.i && std::equal(x_.x, x_.x+long_lag, y_.x); }
169
170 /**
171 * Returns true if the two generators will produce different
172 * sequences of outputs.
173 */
174 BOOST_RANDOM_DETAIL_INEQUALITY_OPERATOR(lagged_fibonacci_engine)
175
176private:
177 /// \cond show_private
178 void fill();
179 /// \endcond
180
181 unsigned int i;
182 UIntType x[long_lag];
183};
184
185#ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION
186// A definition is required even for integral static constants
187template<class UIntType, int w, unsigned int p, unsigned int q>
188const bool lagged_fibonacci_engine<UIntType, w, p, q>::has_fixed_range;
189template<class UIntType, int w, unsigned int p, unsigned int q>
190const unsigned int lagged_fibonacci_engine<UIntType, w, p, q>::long_lag;
191template<class UIntType, int w, unsigned int p, unsigned int q>
192const unsigned int lagged_fibonacci_engine<UIntType, w, p, q>::short_lag;
193template<class UIntType, int w, unsigned int p, unsigned int q>
194const UIntType lagged_fibonacci_engine<UIntType, w, p, q>::default_seed;
195#endif
196
197/// \cond show_private
198
199template<class UIntType, int w, unsigned int p, unsigned int q>
200void lagged_fibonacci_engine<UIntType, w, p, q>::fill()
201{
202 // two loops to avoid costly modulo operations
203 { // extra scope for MSVC brokenness w.r.t. for scope
204 for(unsigned int j = 0; j < short_lag; ++j)
205 x[j] = (x[j] + x[j+(long_lag-short_lag)]) & low_bits_mask_t<w>::sig_bits;
206 }
207 for(unsigned int j = short_lag; j < long_lag; ++j)
208 x[j] = (x[j] + x[j-short_lag]) & low_bits_mask_t<w>::sig_bits;
209 i = 0;
210}
211
212/// \endcond
213
214/// \cond show_deprecated
215
216// provided for backwards compatibility
217template<class UIntType, int w, unsigned int p, unsigned int q, UIntType v = 0>
218class lagged_fibonacci : public lagged_fibonacci_engine<UIntType, w, p, q>
219{
220 typedef lagged_fibonacci_engine<UIntType, w, p, q> base_type;
221public:
222 lagged_fibonacci() {}
223 BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(lagged_fibonacci, UIntType, val)
224 { this->seed(val); }
225 BOOST_RANDOM_DETAIL_SEED_SEQ_CONSTRUCTOR(lagged_fibonacci, SeedSeq, seq)
226 { this->seed(seq); }
227 template<class It>
228 lagged_fibonacci(It& first, It last) : base_type(first, last) {}
229};
230
231/// \endcond
232
233// lagged Fibonacci generator for the range [0..1)
234// contributed by Matthias Troyer
235// for p=55, q=24 originally by G. J. Mitchell and D. P. Moore 1958
236
237/**
238 * Instantiations of class template @c lagged_fibonacci_01 model a
239 * \pseudo_random_number_generator. It uses a lagged Fibonacci
240 * algorithm with two lags @c p and @c q, evaluated in floating-point
241 * arithmetic: x(i) = x(i-p) + x(i-q) (mod 1) with p > q. See
242 *
243 * @blockquote
244 * "Uniform random number generators for supercomputers", Richard Brent,
245 * Proc. of Fifth Australian Supercomputer Conference, Melbourne,
246 * Dec. 1992, pp. 704-706.
247 * @endblockquote
248 *
249 * @xmlnote
250 * The quality of the generator crucially depends on the choice
251 * of the parameters. User code should employ one of the sensibly
252 * parameterized generators such as \lagged_fibonacci607 instead.
253 * @endxmlnote
254 *
255 * The generator requires considerable amounts of memory for the storage
256 * of its state array. For example, \lagged_fibonacci607 requires about
257 * 4856 bytes and \lagged_fibonacci44497 requires about 350 KBytes.
258 */
259template<class RealType, int w, unsigned int p, unsigned int q>
260class lagged_fibonacci_01_engine
261{
262public:
263 typedef RealType result_type;
264 BOOST_STATIC_CONSTANT(bool, has_fixed_range = false);
265 BOOST_STATIC_CONSTANT(int, word_size = w);
266 BOOST_STATIC_CONSTANT(unsigned int, long_lag = p);
267 BOOST_STATIC_CONSTANT(unsigned int, short_lag = q);
268
269 BOOST_STATIC_CONSTANT(boost::uint32_t, default_seed = 331u);
270
271 /** Constructs a @c lagged_fibonacci_01 generator and calls @c seed(). */
272 lagged_fibonacci_01_engine() { seed(); }
273 /** Constructs a @c lagged_fibonacci_01 generator and calls @c seed(value). */
274 BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(lagged_fibonacci_01_engine, uint32_t, value)
275 { seed(value); }
276 /** Constructs a @c lagged_fibonacci_01 generator and calls @c seed(gen). */
277 BOOST_RANDOM_DETAIL_SEED_SEQ_CONSTRUCTOR(lagged_fibonacci_01_engine, SeedSeq, seq)
278 { seed(seq); }
279 template<class It> lagged_fibonacci_01_engine(It& first, It last)
280 { seed(first, last); }
281
282 // compiler-generated copy ctor and assignment operator are fine
283
284 /** Calls seed(default_seed). */
285 void seed() { seed(default_seed); }
286
287 /**
288 * Constructs a \minstd_rand0 generator with the constructor parameter
289 * value and calls seed with it. Distinct seeds in the range
290 * [1, 2147483647) will produce generators with different states. Other
291 * seeds will be equivalent to some seed within this range. See
292 * \linear_congruential_engine for details.
293 */
294 BOOST_RANDOM_DETAIL_ARITHMETIC_SEED(lagged_fibonacci_01_engine, boost::uint32_t, value)
295 {
296 minstd_rand0 intgen(value);
297 detail::generator_seed_seq<minstd_rand0> gen(intgen);
298 seed(gen);
299 }
300
301 /**
302 * Seeds this @c lagged_fibonacci_01_engine using values produced by
303 * @c seq.generate.
304 */
305 BOOST_RANDOM_DETAIL_SEED_SEQ_SEED(lagged_fibonacci_01_engine, SeedSeq, seq)
306 {
307 detail::seed_array_real<w>(seq, x);
308 i = long_lag;
309 }
310
311 /**
312 * Seeds this @c lagged_fibonacci_01_engine using values from the
313 * iterator range [first, last). If there are not enough elements
314 * in the range, throws @c std::invalid_argument.
315 */
316 template<class It>
317 void seed(It& first, It last)
318 {
319 detail::fill_array_real<w>(first, last, x);
320 i = long_lag;
321 }
322
323 /** Returns the smallest value that the generator can produce. */
324 static result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () { return result_type(0); }
325 /** Returns the upper bound of the generators outputs. */
326 static result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () { return result_type(1); }
327
328 /** Returns the next value of the generator. */
329 result_type operator()()
330 {
331 if(i >= long_lag)
332 fill();
333 return x[i++];
334 }
335
336 /** Fills a range with random values */
337 template<class Iter>
338 void generate(Iter first, Iter last)
339 { return detail::generate_from_real(*this, first, last); }
340
341 /** Advances the state of the generator by @c z. */
342 void discard(boost::uintmax_t z)
343 {
344 for(boost::uintmax_t j = 0; j < z; ++j) {
345 (*this)();
346 }
347 }
348
349 /**
350 * Writes the textual representation of the generator to a @c std::ostream.
351 */
352 BOOST_RANDOM_DETAIL_OSTREAM_OPERATOR(os, lagged_fibonacci_01_engine, f)
353 {
354 // allow for Koenig lookup
355 using std::pow;
356 os << f.i;
357 std::ios_base::fmtflags oldflags = os.flags(os.dec | os.fixed | os.left);
358 for(unsigned int j = 0; j < f.long_lag; ++j)
359 os << ' ' << f.x[j] * f.modulus();
360 os.flags(oldflags);
361 return os;
362 }
363
364 /**
365 * Reads the textual representation of the generator from a @c std::istream.
366 */
367 BOOST_RANDOM_DETAIL_ISTREAM_OPERATOR(is, lagged_fibonacci_01_engine, f)
368 {
369 is >> f.i;
370 for(unsigned int j = 0; j < f.long_lag; ++j) {
371 typename lagged_fibonacci_01_engine::result_type value;
372 is >> std::ws >> value;
373 f.x[j] = value / f.modulus();
374 }
375 return is;
376 }
377
378 /**
379 * Returns true if the two generators will produce identical
380 * sequences of outputs.
381 */
382 BOOST_RANDOM_DETAIL_EQUALITY_OPERATOR(lagged_fibonacci_01_engine, x_, y_)
383 { return x_.i == y_.i && std::equal(x_.x, x_.x+long_lag, y_.x); }
384
385 /**
386 * Returns true if the two generators will produce different
387 * sequences of outputs.
388 */
389 BOOST_RANDOM_DETAIL_INEQUALITY_OPERATOR(lagged_fibonacci_01_engine)
390
391private:
392 /// \cond show_private
393 void fill();
394 static RealType modulus()
395 {
396 using std::pow;
397 return pow(RealType(2), word_size);
398 }
399 /// \endcond
400 unsigned int i;
401 RealType x[long_lag];
402};
403
404#ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION
405// A definition is required even for integral static constants
406template<class RealType, int w, unsigned int p, unsigned int q>
407const bool lagged_fibonacci_01_engine<RealType, w, p, q>::has_fixed_range;
408template<class RealType, int w, unsigned int p, unsigned int q>
409const unsigned int lagged_fibonacci_01_engine<RealType, w, p, q>::long_lag;
410template<class RealType, int w, unsigned int p, unsigned int q>
411const unsigned int lagged_fibonacci_01_engine<RealType, w, p, q>::short_lag;
412template<class RealType, int w, unsigned int p, unsigned int q>
413const int lagged_fibonacci_01_engine<RealType,w,p,q>::word_size;
414template<class RealType, int w, unsigned int p, unsigned int q>
415const boost::uint32_t lagged_fibonacci_01_engine<RealType,w,p,q>::default_seed;
416#endif
417
418/// \cond show_private
419template<class RealType, int w, unsigned int p, unsigned int q>
420void lagged_fibonacci_01_engine<RealType, w, p, q>::fill()
421{
422 // two loops to avoid costly modulo operations
423 { // extra scope for MSVC brokenness w.r.t. for scope
424 for(unsigned int j = 0; j < short_lag; ++j) {
425 RealType t = x[j] + x[j+(long_lag-short_lag)];
426 if(t >= RealType(1))
427 t -= RealType(1);
428 x[j] = t;
429 }
430 }
431 for(unsigned int j = short_lag; j < long_lag; ++j) {
432 RealType t = x[j] + x[j-short_lag];
433 if(t >= RealType(1))
434 t -= RealType(1);
435 x[j] = t;
436 }
437 i = 0;
438}
439/// \endcond
440
441/// \cond show_deprecated
442
443// provided for backwards compatibility
444template<class RealType, int w, unsigned int p, unsigned int q>
445class lagged_fibonacci_01 : public lagged_fibonacci_01_engine<RealType, w, p, q>
446{
447 typedef lagged_fibonacci_01_engine<RealType, w, p, q> base_type;
448public:
449 lagged_fibonacci_01() {}
450 BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(lagged_fibonacci_01, boost::uint32_t, val)
451 { this->seed(val); }
452 BOOST_RANDOM_DETAIL_SEED_SEQ_CONSTRUCTOR(lagged_fibonacci_01, SeedSeq, seq)
453 { this->seed(seq); }
454 template<class It>
455 lagged_fibonacci_01(It& first, It last) : base_type(first, last) {}
456};
457
458/// \endcond
459
460namespace detail {
461
462template<class Engine>
463struct generator_bits;
464
465template<class RealType, int w, unsigned int p, unsigned int q>
466struct generator_bits<lagged_fibonacci_01_engine<RealType, w, p, q> >
467{
468 static std::size_t value() { return w; }
469};
470
471template<class RealType, int w, unsigned int p, unsigned int q>
472struct generator_bits<lagged_fibonacci_01<RealType, w, p, q> >
473{
474 static std::size_t value() { return w; }
475};
476
477}
478
479#ifdef BOOST_RANDOM_DOXYGEN
480namespace detail {
481/**
482 * The specializations lagged_fibonacci607 ... lagged_fibonacci44497
483 * use well tested lags.
484 *
485 * See
486 *
487 * @blockquote
488 * "On the Periods of Generalized Fibonacci Recurrences", Richard P. Brent
489 * Computer Sciences Laboratory Australian National University, December 1992
490 * @endblockquote
491 *
492 * The lags used here can be found in
493 *
494 * @blockquote
495 * "Uniform random number generators for supercomputers", Richard Brent,
496 * Proc. of Fifth Australian Supercomputer Conference, Melbourne,
497 * Dec. 1992, pp. 704-706.
498 * @endblockquote
499 */
500struct lagged_fibonacci_doc {};
501}
502#endif
503
504/** @copydoc boost::random::detail::lagged_fibonacci_doc */
505typedef lagged_fibonacci_01_engine<double, 48, 607, 273> lagged_fibonacci607;
506/** @copydoc boost::random::detail::lagged_fibonacci_doc */
507typedef lagged_fibonacci_01_engine<double, 48, 1279, 418> lagged_fibonacci1279;
508/** @copydoc boost::random::detail::lagged_fibonacci_doc */
509typedef lagged_fibonacci_01_engine<double, 48, 2281, 1252> lagged_fibonacci2281;
510/** @copydoc boost::random::detail::lagged_fibonacci_doc */
511typedef lagged_fibonacci_01_engine<double, 48, 3217, 576> lagged_fibonacci3217;
512/** @copydoc boost::random::detail::lagged_fibonacci_doc */
513typedef lagged_fibonacci_01_engine<double, 48, 4423, 2098> lagged_fibonacci4423;
514/** @copydoc boost::random::detail::lagged_fibonacci_doc */
515typedef lagged_fibonacci_01_engine<double, 48, 9689, 5502> lagged_fibonacci9689;
516/** @copydoc boost::random::detail::lagged_fibonacci_doc */
517typedef lagged_fibonacci_01_engine<double, 48, 19937, 9842> lagged_fibonacci19937;
518/** @copydoc boost::random::detail::lagged_fibonacci_doc */
519typedef lagged_fibonacci_01_engine<double, 48, 23209, 13470> lagged_fibonacci23209;
520/** @copydoc boost::random::detail::lagged_fibonacci_doc */
521typedef lagged_fibonacci_01_engine<double, 48, 44497, 21034> lagged_fibonacci44497;
522
523} // namespace random
524
525using random::lagged_fibonacci607;
526using random::lagged_fibonacci1279;
527using random::lagged_fibonacci2281;
528using random::lagged_fibonacci3217;
529using random::lagged_fibonacci4423;
530using random::lagged_fibonacci9689;
531using random::lagged_fibonacci19937;
532using random::lagged_fibonacci23209;
533using random::lagged_fibonacci44497;
534
535} // namespace boost
536
537#endif // BOOST_RANDOM_LAGGED_FIBONACCI_HPP
538

source code of boost/boost/random/lagged_fibonacci.hpp