Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-01-18 09:51:11 

0001 /* boost random/lagged_fibonacci.hpp header file
0002  *
0003  * Copyright Jens Maurer 2000-2001
0004  * Distributed under the Boost Software License, Version 1.0. (See
0005  * accompanying file LICENSE_1_0.txt or copy at
0006  * http://www.boost.org/LICENSE_1_0.txt)
0007  *
0008  * See http://www.boost.org for most recent version including documentation.
0009  *
0010  * $Id$
0011  *
0012  * Revision history
0013  *  2013-10-14  fixed some warnings with Wshadow (mgaunard)
0014  *  2001-02-18  moved to individual header files
0015  */
0016 
0017 #ifndef BOOST_RANDOM_LAGGED_FIBONACCI_HPP
0018 #define BOOST_RANDOM_LAGGED_FIBONACCI_HPP
0019 
0020 #include <istream>
0021 #include <iosfwd>
0022 #include <algorithm>     // std::max
0023 #include <iterator>
0024 #include <boost/config/no_tr1/cmath.hpp>         // std::pow
0025 #include <boost/config.hpp>
0026 #include <boost/limits.hpp>
0027 #include <boost/cstdint.hpp>
0028 #include <boost/integer/integer_mask.hpp>
0029 #include <boost/random/linear_congruential.hpp>
0030 #include <boost/random/uniform_01.hpp>
0031 #include <boost/random/detail/config.hpp>
0032 #include <boost/random/detail/seed.hpp>
0033 #include <boost/random/detail/operators.hpp>
0034 #include <boost/random/detail/generator_seed_seq.hpp>
0035 
0036 namespace boost {
0037 namespace random {
0038 
0039 /**
0040  * Instantiations of class template \lagged_fibonacci_engine model a
0041  * \pseudo_random_number_generator. It uses a lagged Fibonacci
0042  * algorithm with two lags @c p and @c q:
0043  * x(i) = x(i-p) + x(i-q) (mod 2<sup>w</sup>) with p > q.
0044  */
0045 template<class UIntType, int w, unsigned int p, unsigned int q>
0046 class lagged_fibonacci_engine
0047 {
0048 public:
0049     typedef UIntType result_type;
0050     BOOST_STATIC_CONSTANT(bool, has_fixed_range = false);
0051     BOOST_STATIC_CONSTANT(int, word_size = w);
0052     BOOST_STATIC_CONSTANT(unsigned int, long_lag = p);
0053     BOOST_STATIC_CONSTANT(unsigned int, short_lag = q);
0054 
0055     BOOST_STATIC_CONSTANT(UIntType, default_seed = 331u);
0056 
0057     /** Returns the smallest value that the generator can produce. */
0058     static BOOST_CONSTEXPR result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () { return 0; }
0059     /** Returns the largest value that the generator can produce. */
0060     static BOOST_CONSTEXPR result_type max BOOST_PREVENT_MACRO_SUBSTITUTION ()
0061     { return low_bits_mask_t<w>::sig_bits; }
0062 
0063     /** Creates a new @c lagged_fibonacci_engine and calls @c seed(). */
0064     lagged_fibonacci_engine() { seed(); }
0065 
0066     /** Creates a new @c lagged_fibonacci_engine and calls @c seed(value). */
0067     BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(lagged_fibonacci_engine,
0068         UIntType, value)
0069     { seed(value); }
0070 
0071     /** Creates a new @c lagged_fibonacci_engine and calls @c seed(seq). */
0072     BOOST_RANDOM_DETAIL_SEED_SEQ_CONSTRUCTOR(lagged_fibonacci_engine,
0073         SeedSeq, seq)
0074     { seed(seq); }
0075 
0076     /**
0077      * Creates a new @c lagged_fibonacci_engine and calls @c seed(first, last).
0078      */
0079     template<class It> lagged_fibonacci_engine(It& first, It last)
0080     { seed(first, last); }
0081 
0082     // compiler-generated copy ctor and assignment operator are fine
0083 
0084     /** Calls @c seed(default_seed). */
0085     void seed() { seed(default_seed); }
0086 
0087     /**
0088      * Sets the state of the generator to values produced by
0089      * a \minstd_rand0 generator.
0090      */
0091     BOOST_RANDOM_DETAIL_ARITHMETIC_SEED(lagged_fibonacci_engine,
0092         UIntType, value)
0093     {
0094         minstd_rand0 intgen(static_cast<boost::uint32_t>(value));
0095         detail::generator_seed_seq<minstd_rand0> gen(intgen);
0096         seed(gen);
0097     }
0098 
0099     /**
0100      * Sets the state of the generator using values produced by seq.
0101      */
0102     BOOST_RANDOM_DETAIL_SEED_SEQ_SEED(lagged_fibonacci_engine, SeedSeq, seq)
0103     {
0104         detail::seed_array_int<w>(seq, x);
0105         i = long_lag;
0106     }
0107 
0108     /**
0109      * Sets the state of the generator to values from the iterator
0110      * range [first, last).  If there are not enough elements in the
0111      * range [first, last) throws @c std::invalid_argument.
0112      */
0113     template<class It>
0114     void seed(It& first, It last)
0115     {
0116         detail::fill_array_int<w>(first, last, x);
0117         i = long_lag;
0118     }
0119 
0120     /** Returns the next value of the generator. */
0121     result_type operator()()
0122     {
0123         if(i >= long_lag)
0124             fill();
0125         return x[i++];
0126     }
0127 
0128     /** Fills a range with random values */
0129     template<class Iter>
0130     void generate(Iter first, Iter last)
0131     { detail::generate_from_int(*this, first, last); }
0132 
0133     /** Advances the state of the generator by @c z. */
0134     void discard(boost::uintmax_t z)
0135     {
0136         for(boost::uintmax_t j = 0; j < z; ++j) {
0137             (*this)();
0138         }
0139     }
0140 
0141     /**
0142      * Writes the textual representation of the generator to a @c std::ostream.
0143      */
0144     BOOST_RANDOM_DETAIL_OSTREAM_OPERATOR(os, lagged_fibonacci_engine, f)
0145     {
0146         os << f.i;
0147         for(unsigned int j = 0; j < f.long_lag; ++j)
0148             os << ' ' << f.x[j];
0149         return os;
0150     }
0151 
0152     /**
0153      * Reads the textual representation of the generator from a @c std::istream.
0154      */
0155     BOOST_RANDOM_DETAIL_ISTREAM_OPERATOR(is, lagged_fibonacci_engine, f)
0156     {
0157         is >> f.i >> std::ws;
0158         for(unsigned int j = 0; j < f.long_lag; ++j)
0159             is >> f.x[j] >> std::ws;
0160         return is;
0161     }
0162 
0163     /**
0164      * Returns true if the two generators will produce identical
0165      * sequences of outputs.
0166      */
0167     BOOST_RANDOM_DETAIL_EQUALITY_OPERATOR(lagged_fibonacci_engine, x_, y_)
0168     { return x_.i == y_.i && std::equal(x_.x, x_.x+long_lag, y_.x); }
0169 
0170     /**
0171      * Returns true if the two generators will produce different
0172      * sequences of outputs.
0173      */
0174     BOOST_RANDOM_DETAIL_INEQUALITY_OPERATOR(lagged_fibonacci_engine)
0175 
0176 private:
0177     /// \cond show_private
0178     void fill();
0179     /// \endcond
0180 
0181     unsigned int i;
0182     UIntType x[long_lag];
0183 };
0184 
0185 #ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION
0186 //  A definition is required even for integral static constants
0187 template<class UIntType, int w, unsigned int p, unsigned int q>
0188 const bool lagged_fibonacci_engine<UIntType, w, p, q>::has_fixed_range;
0189 template<class UIntType, int w, unsigned int p, unsigned int q>
0190 const unsigned int lagged_fibonacci_engine<UIntType, w, p, q>::long_lag;
0191 template<class UIntType, int w, unsigned int p, unsigned int q>
0192 const unsigned int lagged_fibonacci_engine<UIntType, w, p, q>::short_lag;
0193 template<class UIntType, int w, unsigned int p, unsigned int q>
0194 const UIntType lagged_fibonacci_engine<UIntType, w, p, q>::default_seed;
0195 #endif
0196 
0197 /// \cond show_private
0198 
0199 template<class UIntType, int w, unsigned int p, unsigned int q>
0200 void lagged_fibonacci_engine<UIntType, w, p, q>::fill()
0201 {
0202     // two loops to avoid costly modulo operations
0203     {  // extra scope for MSVC brokenness w.r.t. for scope
0204     for(unsigned int j = 0; j < short_lag; ++j)
0205         x[j] = (x[j] + x[j+(long_lag-short_lag)]) & low_bits_mask_t<w>::sig_bits;
0206     }
0207     for(unsigned int j = short_lag; j < long_lag; ++j)
0208         x[j] = (x[j] + x[j-short_lag]) & low_bits_mask_t<w>::sig_bits;
0209     i = 0;
0210 }
0211 
0212 /// \endcond
0213 
0214 /// \cond show_deprecated
0215 
0216 // provided for backwards compatibility
0217 template<class UIntType, int w, unsigned int p, unsigned int q, UIntType v = 0>
0218 class lagged_fibonacci : public lagged_fibonacci_engine<UIntType, w, p, q>
0219 {
0220     typedef lagged_fibonacci_engine<UIntType, w, p, q> base_type;
0221 public:
0222     lagged_fibonacci() {}
0223     BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(lagged_fibonacci, UIntType, val)
0224     { this->seed(val); }
0225     BOOST_RANDOM_DETAIL_SEED_SEQ_CONSTRUCTOR(lagged_fibonacci, SeedSeq, seq)
0226     { this->seed(seq); }
0227     template<class It>
0228     lagged_fibonacci(It& first, It last) : base_type(first, last) {}
0229 };
0230 
0231 /// \endcond
0232 
0233 // lagged Fibonacci generator for the range [0..1)
0234 // contributed by Matthias Troyer
0235 // for p=55, q=24 originally by G. J. Mitchell and D. P. Moore 1958
0236 
0237 /**
0238  * Instantiations of class template @c lagged_fibonacci_01 model a
0239  * \pseudo_random_number_generator. It uses a lagged Fibonacci
0240  * algorithm with two lags @c p and @c q, evaluated in floating-point
0241  * arithmetic: x(i) = x(i-p) + x(i-q) (mod 1) with p > q. See
0242  *
0243  *  @blockquote
0244  *  "Uniform random number generators for supercomputers", Richard Brent,
0245  *  Proc. of Fifth Australian Supercomputer Conference, Melbourne,
0246  *  Dec. 1992, pp. 704-706.
0247  *  @endblockquote
0248  *
0249  * @xmlnote
0250  * The quality of the generator crucially depends on the choice
0251  * of the parameters. User code should employ one of the sensibly
0252  * parameterized generators such as \lagged_fibonacci607 instead.
0253  * @endxmlnote
0254  *
0255  * The generator requires considerable amounts of memory for the storage
0256  * of its state array. For example, \lagged_fibonacci607 requires about
0257  * 4856 bytes and \lagged_fibonacci44497 requires about 350 KBytes.
0258  */
0259 template<class RealType, int w, unsigned int p, unsigned int q>
0260 class lagged_fibonacci_01_engine
0261 {
0262 public:
0263     typedef RealType result_type;
0264     BOOST_STATIC_CONSTANT(bool, has_fixed_range = false);
0265     BOOST_STATIC_CONSTANT(int, word_size = w);
0266     BOOST_STATIC_CONSTANT(unsigned int, long_lag = p);
0267     BOOST_STATIC_CONSTANT(unsigned int, short_lag = q);
0268 
0269     BOOST_STATIC_CONSTANT(boost::uint32_t, default_seed = 331u);
0270 
0271     /** Constructs a @c lagged_fibonacci_01 generator and calls @c seed(). */
0272     lagged_fibonacci_01_engine() { seed(); }
0273     /** Constructs a @c lagged_fibonacci_01 generator and calls @c seed(value). */
0274     BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(lagged_fibonacci_01_engine, uint32_t, value)
0275     { seed(value); }
0276     /** Constructs a @c lagged_fibonacci_01 generator and calls @c seed(gen). */
0277     BOOST_RANDOM_DETAIL_SEED_SEQ_CONSTRUCTOR(lagged_fibonacci_01_engine, SeedSeq, seq)
0278     { seed(seq); }
0279     template<class It> lagged_fibonacci_01_engine(It& first, It last)
0280     { seed(first, last); }
0281 
0282     // compiler-generated copy ctor and assignment operator are fine
0283 
0284     /** Calls seed(default_seed). */
0285     void seed() { seed(default_seed); }
0286 
0287     /**
0288      * Constructs a \minstd_rand0 generator with the constructor parameter
0289      * value and calls seed with it. Distinct seeds in the range
0290      * [1, 2147483647) will produce generators with different states. Other
0291      * seeds will be equivalent to some seed within this range. See
0292      * \linear_congruential_engine for details.
0293      */
0294     BOOST_RANDOM_DETAIL_ARITHMETIC_SEED(lagged_fibonacci_01_engine, boost::uint32_t, value)
0295     {
0296         minstd_rand0 intgen(value);
0297         detail::generator_seed_seq<minstd_rand0> gen(intgen);
0298         seed(gen);
0299     }
0300 
0301     /**
0302      * Seeds this @c lagged_fibonacci_01_engine using values produced by
0303      * @c seq.generate.
0304      */
0305     BOOST_RANDOM_DETAIL_SEED_SEQ_SEED(lagged_fibonacci_01_engine, SeedSeq, seq)
0306     {
0307         detail::seed_array_real<w>(seq, x);
0308         i = long_lag;
0309     }
0310 
0311     /**
0312      * Seeds this @c lagged_fibonacci_01_engine using values from the
0313      * iterator range [first, last).  If there are not enough elements
0314      * in the range, throws @c std::invalid_argument.
0315      */
0316     template<class It>
0317     void seed(It& first, It last)
0318     {
0319         detail::fill_array_real<w>(first, last, x);
0320         i = long_lag;
0321     }
0322 
0323     /** Returns the smallest value that the generator can produce. */
0324     static BOOST_CONSTEXPR result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () { return result_type(0); }
0325     /** Returns the upper bound of the generators outputs. */
0326     static BOOST_CONSTEXPR result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () { return result_type(1); }
0327 
0328     /** Returns the next value of the generator. */
0329     result_type operator()()
0330     {
0331         if(i >= long_lag)
0332             fill();
0333         return x[i++];
0334     }
0335 
0336     /** Fills a range with random values */
0337     template<class Iter>
0338     void generate(Iter first, Iter last)
0339     { return detail::generate_from_real(*this, first, last); }
0340 
0341     /** Advances the state of the generator by @c z. */
0342     void discard(boost::uintmax_t z)
0343     {
0344         for(boost::uintmax_t j = 0; j < z; ++j) {
0345             (*this)();
0346         }
0347     }
0348 
0349     /**
0350      * Writes the textual representation of the generator to a @c std::ostream.
0351      */
0352     BOOST_RANDOM_DETAIL_OSTREAM_OPERATOR(os, lagged_fibonacci_01_engine, f)
0353     {
0354         // allow for Koenig lookup
0355         using std::pow;
0356         os << f.i;
0357         std::ios_base::fmtflags oldflags = os.flags(os.dec | os.fixed | os.left);
0358         for(unsigned int j = 0; j < f.long_lag; ++j)
0359             os << ' ' << f.x[j] * f.modulus();
0360         os.flags(oldflags);
0361         return os;
0362     }
0363 
0364     /**
0365      * Reads the textual representation of the generator from a @c std::istream.
0366      */
0367     BOOST_RANDOM_DETAIL_ISTREAM_OPERATOR(is, lagged_fibonacci_01_engine, f)
0368     {
0369         is >> f.i;
0370         for(unsigned int j = 0; j < f.long_lag; ++j) {
0371             typename lagged_fibonacci_01_engine::result_type value;
0372             is >> std::ws >> value;
0373             f.x[j] = value / f.modulus();
0374         }
0375         return is;
0376     }
0377 
0378     /**
0379      * Returns true if the two generators will produce identical
0380      * sequences of outputs.
0381      */
0382     BOOST_RANDOM_DETAIL_EQUALITY_OPERATOR(lagged_fibonacci_01_engine, x_, y_)
0383     { return x_.i == y_.i && std::equal(x_.x, x_.x+long_lag, y_.x); }
0384 
0385     /**
0386      * Returns true if the two generators will produce different
0387      * sequences of outputs.
0388      */
0389     BOOST_RANDOM_DETAIL_INEQUALITY_OPERATOR(lagged_fibonacci_01_engine)
0390 
0391 private:
0392     /// \cond show_private
0393     void fill();
0394     static RealType modulus()
0395     {
0396         using std::pow;
0397         return pow(RealType(2), word_size);
0398     }
0399     /// \endcond
0400     unsigned int i;
0401     RealType x[long_lag];
0402 };
0403 
0404 #ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION
0405 //  A definition is required even for integral static constants
0406 template<class RealType, int w, unsigned int p, unsigned int q>
0407 const bool lagged_fibonacci_01_engine<RealType, w, p, q>::has_fixed_range;
0408 template<class RealType, int w, unsigned int p, unsigned int q>
0409 const unsigned int lagged_fibonacci_01_engine<RealType, w, p, q>::long_lag;
0410 template<class RealType, int w, unsigned int p, unsigned int q>
0411 const unsigned int lagged_fibonacci_01_engine<RealType, w, p, q>::short_lag;
0412 template<class RealType, int w, unsigned int p, unsigned int q>
0413 const int lagged_fibonacci_01_engine<RealType,w,p,q>::word_size;
0414 template<class RealType, int w, unsigned int p, unsigned int q>
0415 const boost::uint32_t lagged_fibonacci_01_engine<RealType,w,p,q>::default_seed;
0416 #endif
0417 
0418 /// \cond show_private
0419 template<class RealType, int w, unsigned int p, unsigned int q>
0420 void lagged_fibonacci_01_engine<RealType, w, p, q>::fill()
0421 {
0422     // two loops to avoid costly modulo operations
0423     {  // extra scope for MSVC brokenness w.r.t. for scope
0424     for(unsigned int j = 0; j < short_lag; ++j) {
0425         RealType t = x[j] + x[j+(long_lag-short_lag)];
0426         if(t >= RealType(1))
0427             t -= RealType(1);
0428         x[j] = t;
0429     }
0430     }
0431     for(unsigned int j = short_lag; j < long_lag; ++j) {
0432         RealType t = x[j] + x[j-short_lag];
0433         if(t >= RealType(1))
0434             t -= RealType(1);
0435         x[j] = t;
0436     }
0437     i = 0;
0438 }
0439 /// \endcond
0440 
0441 /// \cond show_deprecated
0442 
0443 // provided for backwards compatibility
0444 template<class RealType, int w, unsigned int p, unsigned int q>
0445 class lagged_fibonacci_01 : public lagged_fibonacci_01_engine<RealType, w, p, q>
0446 {
0447     typedef lagged_fibonacci_01_engine<RealType, w, p, q> base_type;
0448 public:
0449     lagged_fibonacci_01() {}
0450     BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(lagged_fibonacci_01, boost::uint32_t, val)
0451     { this->seed(val); }
0452     BOOST_RANDOM_DETAIL_SEED_SEQ_CONSTRUCTOR(lagged_fibonacci_01, SeedSeq, seq)
0453     { this->seed(seq); }
0454     template<class It>
0455     lagged_fibonacci_01(It& first, It last) : base_type(first, last) {}
0456 };
0457 
0458 /// \endcond
0459 
0460 namespace detail {
0461 
0462 template<class Engine>
0463 struct generator_bits;
0464 
0465 template<class RealType, int w, unsigned int p, unsigned int q>
0466 struct generator_bits<lagged_fibonacci_01_engine<RealType, w, p, q> >
0467 {
0468     static std::size_t value() { return w; }
0469 };
0470 
0471 template<class RealType, int w, unsigned int p, unsigned int q>
0472 struct generator_bits<lagged_fibonacci_01<RealType, w, p, q> >
0473 {
0474     static std::size_t value() { return w; }
0475 };
0476 
0477 }
0478 
0479 #ifdef BOOST_RANDOM_DOXYGEN
0480 namespace detail {
0481 /**
0482  * The specializations lagged_fibonacci607 ... lagged_fibonacci44497
0483  * use well tested lags.
0484  *
0485  * See
0486  *
0487  *  @blockquote
0488  *  "On the Periods of Generalized Fibonacci Recurrences", Richard P. Brent
0489  *  Computer Sciences Laboratory Australian National University, December 1992
0490  *  @endblockquote
0491  *
0492  * The lags used here can be found in
0493  *
0494  *  @blockquote
0495  *  "Uniform random number generators for supercomputers", Richard Brent,
0496  *  Proc. of Fifth Australian Supercomputer Conference, Melbourne,
0497  *  Dec. 1992, pp. 704-706.
0498  *  @endblockquote
0499  */
0500 struct lagged_fibonacci_doc {};
0501 }
0502 #endif
0503 
0504 /** @copydoc boost::random::detail::lagged_fibonacci_doc */
0505 typedef lagged_fibonacci_01_engine<double, 48, 607, 273> lagged_fibonacci607;
0506 /** @copydoc boost::random::detail::lagged_fibonacci_doc */
0507 typedef lagged_fibonacci_01_engine<double, 48, 1279, 418> lagged_fibonacci1279;
0508 /** @copydoc boost::random::detail::lagged_fibonacci_doc */
0509 typedef lagged_fibonacci_01_engine<double, 48, 2281, 1252> lagged_fibonacci2281;
0510 /** @copydoc boost::random::detail::lagged_fibonacci_doc */
0511 typedef lagged_fibonacci_01_engine<double, 48, 3217, 576> lagged_fibonacci3217;
0512 /** @copydoc boost::random::detail::lagged_fibonacci_doc */
0513 typedef lagged_fibonacci_01_engine<double, 48, 4423, 2098> lagged_fibonacci4423;
0514 /** @copydoc boost::random::detail::lagged_fibonacci_doc */
0515 typedef lagged_fibonacci_01_engine<double, 48, 9689, 5502> lagged_fibonacci9689;
0516 /** @copydoc boost::random::detail::lagged_fibonacci_doc */
0517 typedef lagged_fibonacci_01_engine<double, 48, 19937, 9842> lagged_fibonacci19937;
0518 /** @copydoc boost::random::detail::lagged_fibonacci_doc */
0519 typedef lagged_fibonacci_01_engine<double, 48, 23209, 13470> lagged_fibonacci23209;
0520 /** @copydoc boost::random::detail::lagged_fibonacci_doc */
0521 typedef lagged_fibonacci_01_engine<double, 48, 44497, 21034> lagged_fibonacci44497;
0522 
0523 } // namespace random
0524 
0525 using random::lagged_fibonacci607;
0526 using random::lagged_fibonacci1279;
0527 using random::lagged_fibonacci2281;
0528 using random::lagged_fibonacci3217;
0529 using random::lagged_fibonacci4423;
0530 using random::lagged_fibonacci9689;
0531 using random::lagged_fibonacci19937;
0532 using random::lagged_fibonacci23209;
0533 using random::lagged_fibonacci44497;
0534 
0535 } // namespace boost
0536 
0537 #endif // BOOST_RANDOM_LAGGED_FIBONACCI_HPP
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!