boost/random/lagged_fibonacci.hpp
/* boost random/lagged_fibonacci.hpp header file
*
* Copyright Jens Maurer 2000-2001
* 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: lagged_fibonacci.hpp 72951 2011-07-07 04:57:37Z steven_watanabe $
*
* Revision history
* 2001-02-18 moved to individual header files
*/
#ifndef BOOST_RANDOM_LAGGED_FIBONACCI_HPP
#define BOOST_RANDOM_LAGGED_FIBONACCI_HPP
#include <istream>
#include <iosfwd>
#include <algorithm> // std::max
#include <iterator>
#include <boost/config/no_tr1/cmath.hpp> // std::pow
#include <boost/config.hpp>
#include <boost/limits.hpp>
#include <boost/cstdint.hpp>
#include <boost/integer/integer_mask.hpp>
#include <boost/random/linear_congruential.hpp>
#include <boost/random/uniform_01.hpp>
#include <boost/random/detail/config.hpp>
#include <boost/random/detail/seed.hpp>
#include <boost/random/detail/operators.hpp>
#include <boost/random/detail/generator_seed_seq.hpp>
namespace boost {
namespace random {
/**
* Instantiations of class template \lagged_fibonacci_engine model a
* \pseudo_random_number_generator. It uses a lagged Fibonacci
* algorithm with two lags @c p and @c q:
* x(i) = x(i-p) + x(i-q) (mod 2<sup>w</sup>) with p > q.
*/
template<class UIntType, int w, unsigned int p, unsigned int q>
class lagged_fibonacci_engine
{
public:
typedef UIntType result_type;
BOOST_STATIC_CONSTANT(bool, has_fixed_range = false);
BOOST_STATIC_CONSTANT(int, word_size = w);
BOOST_STATIC_CONSTANT(unsigned int, long_lag = p);
BOOST_STATIC_CONSTANT(unsigned int, short_lag = q);
BOOST_STATIC_CONSTANT(UIntType, default_seed = 331u);
/** 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 low_bits_mask_t<w>::sig_bits; }
/** Creates a new @c lagged_fibonacci_engine and calls @c seed(). */
lagged_fibonacci_engine() { seed(); }
/** Creates a new @c lagged_fibonacci_engine and calls @c seed(value). */
BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(lagged_fibonacci_engine,
UIntType, value)
{ seed(value); }
/** Creates a new @c lagged_fibonacci_engine and calls @c seed(seq). */
BOOST_RANDOM_DETAIL_SEED_SEQ_CONSTRUCTOR(lagged_fibonacci_engine,
SeedSeq, seq)
{ seed(seq); }
/**
* Creates a new @c lagged_fibonacci_engine and calls @c seed(first, last).
*/
template<class It> lagged_fibonacci_engine(It& first, It last)
{ seed(first, last); }
// compiler-generated copy ctor and assignment operator are fine
/** Calls @c seed(default_seed). */
void seed() { seed(default_seed); }
/**
* Sets the state of the generator to values produced by
* a \minstd_rand0 generator.
*/
BOOST_RANDOM_DETAIL_ARITHMETIC_SEED(lagged_fibonacci_engine,
UIntType, value)
{
minstd_rand0 intgen(static_cast<boost::uint32_t>(value));
detail::generator_seed_seq<minstd_rand0> gen(intgen);
seed(gen);
}
/**
* Sets the state of the generator using values produced by seq.
*/
BOOST_RANDOM_DETAIL_SEED_SEQ_SEED(lagged_fibonacci_engine, SeedSeq, seq)
{
detail::seed_array_int<w>(seq, x);
i = long_lag;
}
/**
* Sets the state of the generator to values from the iterator
* range [first, last). If there are not enough elements in the
* range [first, last) throws @c std::invalid_argument.
*/
template<class It>
void seed(It& first, It last)
{
detail::fill_array_int<w>(first, last, x);
i = long_lag;
}
/** Returns the next value of the generator. */
result_type operator()()
{
if(i >= long_lag)
fill();
return x[i++];
}
/** 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, lagged_fibonacci_engine, f)
{
os << f.i;
for(unsigned int i = 0; i < f.long_lag; ++i)
os << ' ' << f.x[i];
return os;
}
/**
* Reads the textual representation of the generator from a @c std::istream.
*/
BOOST_RANDOM_DETAIL_ISTREAM_OPERATOR(is, lagged_fibonacci_engine, f)
{
is >> f.i >> std::ws;
for(unsigned int i = 0; i < f.long_lag; ++i)
is >> f.x[i] >> std::ws;
return is;
}
/**
* Returns true if the two generators will produce identical
* sequences of outputs.
*/
BOOST_RANDOM_DETAIL_EQUALITY_OPERATOR(lagged_fibonacci_engine, x, y)
{ return x.i == y.i && std::equal(x.x, x.x+long_lag, y.x); }
/**
* Returns true if the two generators will produce different
* sequences of outputs.
*/
BOOST_RANDOM_DETAIL_INEQUALITY_OPERATOR(lagged_fibonacci_engine)
private:
/// \cond show_private
void fill();
/// \endcond
unsigned int i;
UIntType x[long_lag];
};
#ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION
// A definition is required even for integral static constants
template<class UIntType, int w, unsigned int p, unsigned int q>
const bool lagged_fibonacci_engine<UIntType, w, p, q>::has_fixed_range;
template<class UIntType, int w, unsigned int p, unsigned int q>
const unsigned int lagged_fibonacci_engine<UIntType, w, p, q>::long_lag;
template<class UIntType, int w, unsigned int p, unsigned int q>
const unsigned int lagged_fibonacci_engine<UIntType, w, p, q>::short_lag;
template<class UIntType, int w, unsigned int p, unsigned int q>
const UIntType lagged_fibonacci_engine<UIntType, w, p, q>::default_seed;
#endif
/// \cond show_private
template<class UIntType, int w, unsigned int p, unsigned int q>
void lagged_fibonacci_engine<UIntType, w, p, q>::fill()
{
// two loops to avoid costly modulo operations
{ // extra scope for MSVC brokenness w.r.t. for scope
for(unsigned int j = 0; j < short_lag; ++j)
x[j] = (x[j] + x[j+(long_lag-short_lag)]) & low_bits_mask_t<w>::sig_bits;
}
for(unsigned int j = short_lag; j < long_lag; ++j)
x[j] = (x[j] + x[j-short_lag]) & low_bits_mask_t<w>::sig_bits;
i = 0;
}
/// \endcond
/// \cond show_deprecated
// provided for backwards compatibility
template<class UIntType, int w, unsigned int p, unsigned int q, UIntType v = 0>
class lagged_fibonacci : public lagged_fibonacci_engine<UIntType, w, p, q>
{
typedef lagged_fibonacci_engine<UIntType, w, p, q> base_type;
public:
lagged_fibonacci() {}
BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(lagged_fibonacci, UIntType, val)
{ this->seed(val); }
BOOST_RANDOM_DETAIL_SEED_SEQ_CONSTRUCTOR(lagged_fibonacci, SeedSeq, seq)
{ this->seed(seq); }
template<class It>
lagged_fibonacci(It& first, It last) : base_type(first, last) {}
};
/// \endcond
// lagged Fibonacci generator for the range [0..1)
// contributed by Matthias Troyer
// for p=55, q=24 originally by G. J. Mitchell and D. P. Moore 1958
/**
* Instantiations of class template @c lagged_fibonacci_01 model a
* \pseudo_random_number_generator. It uses a lagged Fibonacci
* algorithm with two lags @c p and @c q, evaluated in floating-point
* arithmetic: x(i) = x(i-p) + x(i-q) (mod 1) with p > q. See
*
* @blockquote
* "Uniform random number generators for supercomputers", Richard Brent,
* Proc. of Fifth Australian Supercomputer Conference, Melbourne,
* Dec. 1992, pp. 704-706.
* @endblockquote
*
* @xmlnote
* The quality of the generator crucially depends on the choice
* of the parameters. User code should employ one of the sensibly
* parameterized generators such as \lagged_fibonacci607 instead.
* @endxmlnote
*
* The generator requires considerable amounts of memory for the storage
* of its state array. For example, \lagged_fibonacci607 requires about
* 4856 bytes and \lagged_fibonacci44497 requires about 350 KBytes.
*/
template<class RealType, int w, unsigned int p, unsigned int q>
class lagged_fibonacci_01_engine
{
public:
typedef RealType result_type;
BOOST_STATIC_CONSTANT(bool, has_fixed_range = false);
BOOST_STATIC_CONSTANT(int, word_size = w);
BOOST_STATIC_CONSTANT(unsigned int, long_lag = p);
BOOST_STATIC_CONSTANT(unsigned int, short_lag = q);
BOOST_STATIC_CONSTANT(boost::uint32_t, default_seed = 331u);
/** Constructs a @c lagged_fibonacci_01 generator and calls @c seed(). */
lagged_fibonacci_01_engine() { seed(); }
/** Constructs a @c lagged_fibonacci_01 generator and calls @c seed(value). */
BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(lagged_fibonacci_01_engine, uint32_t, value)
{ seed(value); }
/** Constructs a @c lagged_fibonacci_01 generator and calls @c seed(gen). */
BOOST_RANDOM_DETAIL_SEED_SEQ_CONSTRUCTOR(lagged_fibonacci_01_engine, SeedSeq, seq)
{ seed(seq); }
template<class It> lagged_fibonacci_01_engine(It& first, It last)
{ seed(first, last); }
// compiler-generated copy ctor and assignment operator are fine
/** Calls seed(default_seed). */
void seed() { seed(default_seed); }
/**
* Constructs a \minstd_rand0 generator with the constructor parameter
* value and calls seed with it. Distinct seeds in the range
* [1, 2147483647) will produce generators with different states. Other
* seeds will be equivalent to some seed within this range. See
* \linear_congruential_engine for details.
*/
BOOST_RANDOM_DETAIL_ARITHMETIC_SEED(lagged_fibonacci_01_engine, boost::uint32_t, value)
{
minstd_rand0 intgen(value);
detail::generator_seed_seq<minstd_rand0> gen(intgen);
seed(gen);
}
/**
* Seeds this @c lagged_fibonacci_01_engine using values produced by
* @c seq.generate.
*/
BOOST_RANDOM_DETAIL_SEED_SEQ_SEED(lagged_fibonacci_01_engine, SeedSeq, seq)
{
detail::seed_array_real<w>(seq, x);
i = long_lag;
}
/**
* Seeds this @c lagged_fibonacci_01_engine using values from the
* iterator range [first, last). If there are not enough elements
* in the range, throws @c std::invalid_argument.
*/
template<class It>
void seed(It& first, It last)
{
detail::fill_array_real<w>(first, last, x);
i = long_lag;
}
/** Returns the smallest value that the generator can produce. */
static result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () { return result_type(0); }
/** Returns the upper bound of the generators outputs. */
static result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () { return result_type(1); }
/** Returns the next value of the generator. */
result_type operator()()
{
if(i >= long_lag)
fill();
return x[i++];
}
/** Fills a range with random values */
template<class Iter>
void generate(Iter first, Iter last)
{ return detail::generate_from_real(*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, lagged_fibonacci_01_engine, f)
{
// allow for Koenig lookup
using std::pow;
os << f.i;
std::ios_base::fmtflags oldflags = os.flags(os.dec | os.fixed | os.left);
for(unsigned int i = 0; i < f.long_lag; ++i)
os << ' ' << f.x[i] * f.modulus();
os.flags(oldflags);
return os;
}
/**
* Reads the textual representation of the generator from a @c std::istream.
*/
BOOST_RANDOM_DETAIL_ISTREAM_OPERATOR(is, lagged_fibonacci_01_engine, f)
{
is >> f.i;
for(unsigned int i = 0; i < f.long_lag; ++i) {
typename lagged_fibonacci_01_engine::result_type value;
is >> std::ws >> value;
f.x[i] = value / f.modulus();
}
return is;
}
/**
* Returns true if the two generators will produce identical
* sequences of outputs.
*/
BOOST_RANDOM_DETAIL_EQUALITY_OPERATOR(lagged_fibonacci_01_engine, x, y)
{ return x.i == y.i && std::equal(x.x, x.x+long_lag, y.x); }
/**
* Returns true if the two generators will produce different
* sequences of outputs.
*/
BOOST_RANDOM_DETAIL_INEQUALITY_OPERATOR(lagged_fibonacci_01_engine)
private:
/// \cond show_private
void fill();
static RealType modulus()
{
using std::pow;
return pow(RealType(2), word_size);
}
/// \endcond
unsigned int i;
RealType x[long_lag];
};
#ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION
// A definition is required even for integral static constants
template<class RealType, int w, unsigned int p, unsigned int q>
const bool lagged_fibonacci_01_engine<RealType, w, p, q>::has_fixed_range;
template<class RealType, int w, unsigned int p, unsigned int q>
const unsigned int lagged_fibonacci_01_engine<RealType, w, p, q>::long_lag;
template<class RealType, int w, unsigned int p, unsigned int q>
const unsigned int lagged_fibonacci_01_engine<RealType, w, p, q>::short_lag;
template<class RealType, int w, unsigned int p, unsigned int q>
const int lagged_fibonacci_01_engine<RealType,w,p,q>::word_size;
template<class RealType, int w, unsigned int p, unsigned int q>
const boost::uint32_t lagged_fibonacci_01_engine<RealType,w,p,q>::default_seed;
#endif
/// \cond show_private
template<class RealType, int w, unsigned int p, unsigned int q>
void lagged_fibonacci_01_engine<RealType, w, p, q>::fill()
{
// two loops to avoid costly modulo operations
{ // extra scope for MSVC brokenness w.r.t. for scope
for(unsigned int j = 0; j < short_lag; ++j) {
RealType t = x[j] + x[j+(long_lag-short_lag)];
if(t >= RealType(1))
t -= RealType(1);
x[j] = t;
}
}
for(unsigned int j = short_lag; j < long_lag; ++j) {
RealType t = x[j] + x[j-short_lag];
if(t >= RealType(1))
t -= RealType(1);
x[j] = t;
}
i = 0;
}
/// \endcond
/// \cond show_deprecated
// provided for backwards compatibility
template<class RealType, int w, unsigned int p, unsigned int q>
class lagged_fibonacci_01 : public lagged_fibonacci_01_engine<RealType, w, p, q>
{
typedef lagged_fibonacci_01_engine<RealType, w, p, q> base_type;
public:
lagged_fibonacci_01() {}
BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(lagged_fibonacci_01, boost::uint32_t, val)
{ this->seed(val); }
BOOST_RANDOM_DETAIL_SEED_SEQ_CONSTRUCTOR(lagged_fibonacci_01, SeedSeq, seq)
{ this->seed(seq); }
template<class It>
lagged_fibonacci_01(It& first, It last) : base_type(first, last) {}
};
/// \endcond
namespace detail {
template<class Engine>
struct generator_bits;
template<class RealType, int w, unsigned int p, unsigned int q>
struct generator_bits<lagged_fibonacci_01_engine<RealType, w, p, q> >
{
static std::size_t value() { return w; }
};
template<class RealType, int w, unsigned int p, unsigned int q>
struct generator_bits<lagged_fibonacci_01<RealType, w, p, q> >
{
static std::size_t value() { return w; }
};
}
#ifdef BOOST_RANDOM_DOXYGEN
namespace detail {
/**
* The specializations lagged_fibonacci607 ... lagged_fibonacci44497
* use well tested lags.
*
* See
*
* @blockquote
* "On the Periods of Generalized Fibonacci Recurrences", Richard P. Brent
* Computer Sciences Laboratory Australian National University, December 1992
* @endblockquote
*
* The lags used here can be found in
*
* @blockquote
* "Uniform random number generators for supercomputers", Richard Brent,
* Proc. of Fifth Australian Supercomputer Conference, Melbourne,
* Dec. 1992, pp. 704-706.
* @endblockquote
*/
struct lagged_fibonacci_doc {};
}
#endif
/** @copydoc boost::random::detail::lagged_fibonacci_doc */
typedef lagged_fibonacci_01_engine<double, 48, 607, 273> lagged_fibonacci607;
/** @copydoc boost::random::detail::lagged_fibonacci_doc */
typedef lagged_fibonacci_01_engine<double, 48, 1279, 418> lagged_fibonacci1279;
/** @copydoc boost::random::detail::lagged_fibonacci_doc */
typedef lagged_fibonacci_01_engine<double, 48, 2281, 1252> lagged_fibonacci2281;
/** @copydoc boost::random::detail::lagged_fibonacci_doc */
typedef lagged_fibonacci_01_engine<double, 48, 3217, 576> lagged_fibonacci3217;
/** @copydoc boost::random::detail::lagged_fibonacci_doc */
typedef lagged_fibonacci_01_engine<double, 48, 4423, 2098> lagged_fibonacci4423;
/** @copydoc boost::random::detail::lagged_fibonacci_doc */
typedef lagged_fibonacci_01_engine<double, 48, 9689, 5502> lagged_fibonacci9689;
/** @copydoc boost::random::detail::lagged_fibonacci_doc */
typedef lagged_fibonacci_01_engine<double, 48, 19937, 9842> lagged_fibonacci19937;
/** @copydoc boost::random::detail::lagged_fibonacci_doc */
typedef lagged_fibonacci_01_engine<double, 48, 23209, 13470> lagged_fibonacci23209;
/** @copydoc boost::random::detail::lagged_fibonacci_doc */
typedef lagged_fibonacci_01_engine<double, 48, 44497, 21034> lagged_fibonacci44497;
} // namespace random
using random::lagged_fibonacci607;
using random::lagged_fibonacci1279;
using random::lagged_fibonacci2281;
using random::lagged_fibonacci3217;
using random::lagged_fibonacci4423;
using random::lagged_fibonacci9689;
using random::lagged_fibonacci19937;
using random::lagged_fibonacci23209;
using random::lagged_fibonacci44497;
} // namespace boost
#endif // BOOST_RANDOM_LAGGED_FIBONACCI_HPP