1 /* boost random/lagged_fibonacci.hpp header file
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)
8 * See http://www.boost.org for most recent version including documentation.
13 * 2013-10-14 fixed some warnings with Wshadow (mgaunard)
14 * 2001-02-18 moved to individual header files
17 #ifndef BOOST_RANDOM_LAGGED_FIBONACCI_HPP
18 #define BOOST_RANDOM_LAGGED_FIBONACCI_HPP
22 #include <algorithm> // std::max
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>
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.
45 template<class UIntType, int w, unsigned int p, unsigned int q>
46 class lagged_fibonacci_engine
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);
55 BOOST_STATIC_CONSTANT(UIntType, default_seed = 331u);
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; }
63 /** Creates a new @c lagged_fibonacci_engine and calls @c seed(). */
64 lagged_fibonacci_engine() { seed(); }
66 /** Creates a new @c lagged_fibonacci_engine and calls @c seed(value). */
67 BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(lagged_fibonacci_engine,
71 /** Creates a new @c lagged_fibonacci_engine and calls @c seed(seq). */
72 BOOST_RANDOM_DETAIL_SEED_SEQ_CONSTRUCTOR(lagged_fibonacci_engine,
77 * Creates a new @c lagged_fibonacci_engine and calls @c seed(first, last).
79 template<class It> lagged_fibonacci_engine(It& first, It last)
80 { seed(first, last); }
82 // compiler-generated copy ctor and assignment operator are fine
84 /** Calls @c seed(default_seed). */
85 void seed() { seed(default_seed); }
88 * Sets the state of the generator to values produced by
89 * a \minstd_rand0 generator.
91 BOOST_RANDOM_DETAIL_ARITHMETIC_SEED(lagged_fibonacci_engine,
94 minstd_rand0 intgen(static_cast<boost::uint32_t>(value));
95 detail::generator_seed_seq<minstd_rand0> gen(intgen);
100 * Sets the state of the generator using values produced by seq.
102 BOOST_RANDOM_DETAIL_SEED_SEQ_SEED(lagged_fibonacci_engine, SeedSeq, seq)
104 detail::seed_array_int<w>(seq, x);
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.
114 void seed(It& first, It last)
116 detail::fill_array_int<w>(first, last, x);
120 /** Returns the next value of the generator. */
121 result_type operator()()
128 /** Fills a range with random values */
130 void generate(Iter first, Iter last)
131 { detail::generate_from_int(*this, first, last); }
133 /** Advances the state of the generator by @c z. */
134 void discard(boost::uintmax_t z)
136 for(boost::uintmax_t j = 0; j < z; ++j) {
142 * Writes the textual representation of the generator to a @c std::ostream.
144 BOOST_RANDOM_DETAIL_OSTREAM_OPERATOR(os, lagged_fibonacci_engine, f)
147 for(unsigned int j = 0; j < f.long_lag; ++j)
153 * Reads the textual representation of the generator from a @c std::istream.
155 BOOST_RANDOM_DETAIL_ISTREAM_OPERATOR(is, lagged_fibonacci_engine, f)
157 is >> f.i >> std::ws;
158 for(unsigned int j = 0; j < f.long_lag; ++j)
159 is >> f.x[j] >> std::ws;
164 * Returns true if the two generators will produce identical
165 * sequences of outputs.
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); }
171 * Returns true if the two generators will produce different
172 * sequences of outputs.
174 BOOST_RANDOM_DETAIL_INEQUALITY_OPERATOR(lagged_fibonacci_engine)
177 /// \cond show_private
182 UIntType x[long_lag];
185 #ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION
186 // A definition is required even for integral static constants
187 template<class UIntType, int w, unsigned int p, unsigned int q>
188 const bool lagged_fibonacci_engine<UIntType, w, p, q>::has_fixed_range;
189 template<class UIntType, int w, unsigned int p, unsigned int q>
190 const unsigned int lagged_fibonacci_engine<UIntType, w, p, q>::long_lag;
191 template<class UIntType, int w, unsigned int p, unsigned int q>
192 const unsigned int lagged_fibonacci_engine<UIntType, w, p, q>::short_lag;
193 template<class UIntType, int w, unsigned int p, unsigned int q>
194 const UIntType lagged_fibonacci_engine<UIntType, w, p, q>::default_seed;
197 /// \cond show_private
199 template<class UIntType, int w, unsigned int p, unsigned int q>
200 void lagged_fibonacci_engine<UIntType, w, p, q>::fill()
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;
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;
214 /// \cond show_deprecated
216 // provided for backwards compatibility
217 template<class UIntType, int w, unsigned int p, unsigned int q, UIntType v = 0>
218 class lagged_fibonacci : public lagged_fibonacci_engine<UIntType, w, p, q>
220 typedef lagged_fibonacci_engine<UIntType, w, p, q> base_type;
222 lagged_fibonacci() {}
223 BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(lagged_fibonacci, UIntType, val)
225 BOOST_RANDOM_DETAIL_SEED_SEQ_CONSTRUCTOR(lagged_fibonacci, SeedSeq, seq)
228 lagged_fibonacci(It& first, It last) : base_type(first, last) {}
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
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
244 * "Uniform random number generators for supercomputers", Richard Brent,
245 * Proc. of Fifth Australian Supercomputer Conference, Melbourne,
246 * Dec. 1992, pp. 704-706.
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.
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.
259 template<class RealType, int w, unsigned int p, unsigned int q>
260 class lagged_fibonacci_01_engine
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);
269 BOOST_STATIC_CONSTANT(boost::uint32_t, default_seed = 331u);
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)
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)
279 template<class It> lagged_fibonacci_01_engine(It& first, It last)
280 { seed(first, last); }
282 // compiler-generated copy ctor and assignment operator are fine
284 /** Calls seed(default_seed). */
285 void seed() { seed(default_seed); }
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.
294 BOOST_RANDOM_DETAIL_ARITHMETIC_SEED(lagged_fibonacci_01_engine, boost::uint32_t, value)
296 minstd_rand0 intgen(value);
297 detail::generator_seed_seq<minstd_rand0> gen(intgen);
302 * Seeds this @c lagged_fibonacci_01_engine using values produced by
305 BOOST_RANDOM_DETAIL_SEED_SEQ_SEED(lagged_fibonacci_01_engine, SeedSeq, seq)
307 detail::seed_array_real<w>(seq, x);
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.
317 void seed(It& first, It last)
319 detail::fill_array_real<w>(first, last, x);
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); }
328 /** Returns the next value of the generator. */
329 result_type operator()()
336 /** Fills a range with random values */
338 void generate(Iter first, Iter last)
339 { return detail::generate_from_real(*this, first, last); }
341 /** Advances the state of the generator by @c z. */
342 void discard(boost::uintmax_t z)
344 for(boost::uintmax_t j = 0; j < z; ++j) {
350 * Writes the textual representation of the generator to a @c std::ostream.
352 BOOST_RANDOM_DETAIL_OSTREAM_OPERATOR(os, lagged_fibonacci_01_engine, f)
354 // allow for Koenig lookup
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();
365 * Reads the textual representation of the generator from a @c std::istream.
367 BOOST_RANDOM_DETAIL_ISTREAM_OPERATOR(is, lagged_fibonacci_01_engine, f)
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();
379 * Returns true if the two generators will produce identical
380 * sequences of outputs.
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); }
386 * Returns true if the two generators will produce different
387 * sequences of outputs.
389 BOOST_RANDOM_DETAIL_INEQUALITY_OPERATOR(lagged_fibonacci_01_engine)
392 /// \cond show_private
394 static RealType modulus()
397 return pow(RealType(2), word_size);
401 RealType x[long_lag];
404 #ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION
405 // A definition is required even for integral static constants
406 template<class RealType, int w, unsigned int p, unsigned int q>
407 const bool lagged_fibonacci_01_engine<RealType, w, p, q>::has_fixed_range;
408 template<class RealType, int w, unsigned int p, unsigned int q>
409 const unsigned int lagged_fibonacci_01_engine<RealType, w, p, q>::long_lag;
410 template<class RealType, int w, unsigned int p, unsigned int q>
411 const unsigned int lagged_fibonacci_01_engine<RealType, w, p, q>::short_lag;
412 template<class RealType, int w, unsigned int p, unsigned int q>
413 const int lagged_fibonacci_01_engine<RealType,w,p,q>::word_size;
414 template<class RealType, int w, unsigned int p, unsigned int q>
415 const boost::uint32_t lagged_fibonacci_01_engine<RealType,w,p,q>::default_seed;
418 /// \cond show_private
419 template<class RealType, int w, unsigned int p, unsigned int q>
420 void lagged_fibonacci_01_engine<RealType, w, p, q>::fill()
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)];
431 for(unsigned int j = short_lag; j < long_lag; ++j) {
432 RealType t = x[j] + x[j-short_lag];
441 /// \cond show_deprecated
443 // provided for backwards compatibility
444 template<class RealType, int w, unsigned int p, unsigned int q>
445 class lagged_fibonacci_01 : public lagged_fibonacci_01_engine<RealType, w, p, q>
447 typedef lagged_fibonacci_01_engine<RealType, w, p, q> base_type;
449 lagged_fibonacci_01() {}
450 BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(lagged_fibonacci_01, boost::uint32_t, val)
452 BOOST_RANDOM_DETAIL_SEED_SEQ_CONSTRUCTOR(lagged_fibonacci_01, SeedSeq, seq)
455 lagged_fibonacci_01(It& first, It last) : base_type(first, last) {}
462 template<class Engine>
463 struct generator_bits;
465 template<class RealType, int w, unsigned int p, unsigned int q>
466 struct generator_bits<lagged_fibonacci_01_engine<RealType, w, p, q> >
468 static std::size_t value() { return w; }
471 template<class RealType, int w, unsigned int p, unsigned int q>
472 struct generator_bits<lagged_fibonacci_01<RealType, w, p, q> >
474 static std::size_t value() { return w; }
479 #ifdef BOOST_RANDOM_DOXYGEN
482 * The specializations lagged_fibonacci607 ... lagged_fibonacci44497
483 * use well tested lags.
488 * "On the Periods of Generalized Fibonacci Recurrences", Richard P. Brent
489 * Computer Sciences Laboratory Australian National University, December 1992
492 * The lags used here can be found in
495 * "Uniform random number generators for supercomputers", Richard Brent,
496 * Proc. of Fifth Australian Supercomputer Conference, Melbourne,
497 * Dec. 1992, pp. 704-706.
500 struct lagged_fibonacci_doc {};
504 /** @copydoc boost::random::detail::lagged_fibonacci_doc */
505 typedef lagged_fibonacci_01_engine<double, 48, 607, 273> lagged_fibonacci607;
506 /** @copydoc boost::random::detail::lagged_fibonacci_doc */
507 typedef lagged_fibonacci_01_engine<double, 48, 1279, 418> lagged_fibonacci1279;
508 /** @copydoc boost::random::detail::lagged_fibonacci_doc */
509 typedef lagged_fibonacci_01_engine<double, 48, 2281, 1252> lagged_fibonacci2281;
510 /** @copydoc boost::random::detail::lagged_fibonacci_doc */
511 typedef lagged_fibonacci_01_engine<double, 48, 3217, 576> lagged_fibonacci3217;
512 /** @copydoc boost::random::detail::lagged_fibonacci_doc */
513 typedef lagged_fibonacci_01_engine<double, 48, 4423, 2098> lagged_fibonacci4423;
514 /** @copydoc boost::random::detail::lagged_fibonacci_doc */
515 typedef lagged_fibonacci_01_engine<double, 48, 9689, 5502> lagged_fibonacci9689;
516 /** @copydoc boost::random::detail::lagged_fibonacci_doc */
517 typedef lagged_fibonacci_01_engine<double, 48, 19937, 9842> lagged_fibonacci19937;
518 /** @copydoc boost::random::detail::lagged_fibonacci_doc */
519 typedef lagged_fibonacci_01_engine<double, 48, 23209, 13470> lagged_fibonacci23209;
520 /** @copydoc boost::random::detail::lagged_fibonacci_doc */
521 typedef lagged_fibonacci_01_engine<double, 48, 44497, 21034> lagged_fibonacci44497;
523 } // namespace random
525 using random::lagged_fibonacci607;
526 using random::lagged_fibonacci1279;
527 using random::lagged_fibonacci2281;
528 using random::lagged_fibonacci3217;
529 using random::lagged_fibonacci4423;
530 using random::lagged_fibonacci9689;
531 using random::lagged_fibonacci19937;
532 using random::lagged_fibonacci23209;
533 using random::lagged_fibonacci44497;
537 #endif // BOOST_RANDOM_LAGGED_FIBONACCI_HPP