...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
boost::random::inversive_congruential_engine
// In header: <boost/random/inversive_congruential.hpp> template<typename IntType, IntType a, IntType b, IntType p> class inversive_congruential_engine { public: // types typedef IntType result_type; // public static functions static constexpr result_type min(); static constexpr result_type max(); // public member functions inversive_congruential_engine(); explicit inversive_congruential_engine(IntType); template<typename SeedSeq> explicit inversive_congruential_engine(SeedSeq &); template<typename It> inversive_congruential_engine(It &, It); void seed(); void seed(IntType); template<typename SeedSeq> void seed(SeedSeq &); template<typename It> void seed(It &, It); IntType operator()(); template<typename Iter> void generate(Iter, Iter); void discard(boost::uintmax_t); // friend functions template<typename CharT, typename Traits> std::basic_ostream< CharT, Traits > & operator<<(std::basic_ostream< CharT, Traits > &, const inversive_congruential_engine &); template<typename CharT, typename Traits> std::basic_istream< CharT, Traits > & operator>>(std::basic_istream< CharT, Traits > &, const inversive_congruential_engine &); bool operator==(const inversive_congruential_engine &, const inversive_congruential_engine &); bool operator!=(const inversive_congruential_engine &, const inversive_congruential_engine &); // public data members static const bool has_fixed_range; static const result_type multiplier; static const result_type increment; static const result_type modulus; static const IntType default_seed; };
Instantiations of class template inversive_congruential_engine
model a pseudo-random number generator . It uses the inversive congruential algorithm (ICG) described in
"Inversive pseudorandom number generators: concepts, results and links", Peter Hellekalek, In: "Proceedings of the 1995 Winter Simulation Conference", C. Alexopoulos, K. Kang, W.R. Lilegdon, and D. Goldsman (editors), 1995, pp. 255-262. ftp://random.mat.sbg.ac.at/pub/data/wsc95.ps
The output sequence is defined by x(n+1) = (a*inv(x(n)) - b) (mod p), where x(0), a, b, and the prime number p are parameters of the generator. The expression inv(k) denotes the multiplicative inverse of k in the field of integer numbers modulo p, with inv(0) := 0.
The template parameter IntType shall denote a signed integral type large enough to hold p; a, b, and p are the parameters of the generators. The template parameter val is the validation value checked by validation.
Note | |
---|---|
The implementation currently uses the Euclidian Algorithm to compute the multiplicative inverse. Therefore, the inversive generators are about 10-20 times slower than the others (see section"performance"). However, the paper talks of only 3x slowdown, so the Euclidian Algorithm is probably not optimal for calculating the multiplicative inverse. |
inversive_congruential_engine
public member functionsinversive_congruential_engine();
Constructs an inversive_congruential_engine
, seeding it with the default seed.
explicit inversive_congruential_engine(IntType x0);
Constructs an inversive_congruential_engine
, seeding it with x0
.
template<typename SeedSeq> explicit inversive_congruential_engine(SeedSeq & seq);
Constructs an inversive_congruential_engine
, seeding it with values produced by a call to seq.generate()
.
template<typename It> inversive_congruential_engine(It & first, It last);
Constructs an inversive_congruential_engine
, seeds it with values taken from the itrator range [first, last), and adjusts first to point to the element after the last one used. If there are not enough elements, throws std::invalid_argument
.
first and last must be input iterators.
void seed();
Calls seed(default_seed)
void seed(IntType x0);
If c mod m is zero and x0 mod m is zero, changes the current value of the generator to 1. Otherwise, changes it to x0 mod m. If c is zero, distinct seeds in the range [1,m) will leave the generator in distinct states. If c is not zero, the range is [0,m).
template<typename SeedSeq> void seed(SeedSeq & seq);
Seeds an inversive_congruential_engine
using values from a SeedSeq.
template<typename It> void seed(It & first, It last);
seeds an inversive_congruential_engine
with values taken from the itrator range [first, last) and adjusts first
to point to the element after the last one used. If there are not enough elements, throws std::invalid_argument
.
first
and last
must be input iterators.
IntType operator()();
Returns the next output of the generator.
template<typename Iter> void generate(Iter first, Iter last);
Fills a range with random values
void discard(boost::uintmax_t z);
Advances the state of the generator by z
.
inversive_congruential_engine
friend functionstemplate<typename CharT, typename Traits> std::basic_ostream< CharT, Traits > & operator<<(std::basic_ostream< CharT, Traits > & os, const inversive_congruential_engine & x);
Writes the textual representation of the generator to a std::ostream
.
template<typename CharT, typename Traits> std::basic_istream< CharT, Traits > & operator>>(std::basic_istream< CharT, Traits > & is, const inversive_congruential_engine & x);
Reads the textual representation of the generator from a std::istream
.
bool operator==(const inversive_congruential_engine & x, const inversive_congruential_engine & y);
Returns true if the two generators will produce identical sequences of outputs.
bool operator!=(const inversive_congruential_engine & lhs, const inversive_congruential_engine & rhs);
Returns true if the two generators will produce different sequences of outputs.