| Home | Libraries | People | FAQ | More

## Class template inversive_congruential_engine

boost::random::inversive_congruential_engine

## Synopsis

    // 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;

      // construct/copy/destruct
      inversive_congruential_engine();
      explicit inversive_congruential_engine(IntType);
      template<typename SeedSeq> explicit inversive_congruential_engine(SeedSeq &);
      template<typename It> inversive_congruential_engine(It &, It);

      // public static functions
      static result_type min();
      static result_type max();

      // public member functions
      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>
        friend std::basic_ostream< CharT, Traits > &
        operator<<(std::basic_ostream< CharT, Traits > &,
                   const inversive_congruential_engine &);
      template<typename CharT, typename Traits>
        friend std::basic_istream< CharT, Traits > &
        operator>>(std::basic_istream< CharT, Traits > &,
                   const inversive_congruential_engine &);
      friend bool operator==(const inversive_congruential_engine &,
                             const inversive_congruential_engine &);
      friend 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;
    };

## Description

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 construct/copy/destruct

1.     inversive_congruential_engine();

   Constructs an ``inversive_congruential_engine``, seeding it with the default seed.

2.     explicit inversive_congruential_engine(IntType x0);

   Constructs an ``inversive_congruential_engine``, seeding it with `x0`.

3.     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()`.

4.     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.

### `inversive_congruential_engine` public static functions

1.     static result_type min();

2.     static result_type max();

### `inversive_congruential_engine` public member functions

1.     void seed();

   Calls seed(default_seed)

2.     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).

3.     template<typename SeedSeq> void seed(SeedSeq & seq);

   Seeds an ``inversive_congruential_engine`` using values from a SeedSeq.

4.     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.

5.     IntType operator()();

   Returns the next output of the generator.

6.     template<typename Iter> void generate(Iter first, Iter last);

   Fills a range with random values

7.     void discard(boost::uintmax_t z);

   Advances the state of the generator by `z`.

### `inversive_congruential_engine` friend functions

1.     template<typename CharT, typename Traits>
         friend 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`.

2.     template<typename CharT, typename Traits>
         friend 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`.

3.     friend bool operator==(const inversive_congruential_engine & x,
                              const inversive_congruential_engine & y);

   Returns true if the two generators will produce identical sequences of outputs.

4.     friend bool operator!=(const inversive_congruential_engine & lhs,
                              const inversive_congruential_engine & rhs);

   Returns true if the two generators will produce different sequences of outputs.