boost/random/inversive_congruential.hpp

0001 /* boost random/inversive_congruential.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  *  2001-02-18  moved to individual header files
0014  */
0015
0016 #ifndef BOOST_RANDOM_INVERSIVE_CONGRUENTIAL_HPP
0017 #define BOOST_RANDOM_INVERSIVE_CONGRUENTIAL_HPP
0018
0019 #include <iosfwd>
0020 #include <stdexcept>
0021 #include <boost/assert.hpp>
0022 #include <boost/config.hpp>
0023 #include <boost/cstdint.hpp>
0024 #include <boost/random/detail/config.hpp>
0025 #include <boost/random/detail/const_mod.hpp>
0026 #include <boost/random/detail/seed.hpp>
0027 #include <boost/random/detail/operators.hpp>
0028 #include <boost/random/detail/seed_impl.hpp>
0029
0030 #include <boost/random/detail/disable_warnings.hpp>
0031
0032 namespace boost {
0033 namespace random {
0034
0035 // Eichenauer and Lehn 1986
0036 /**
0037  * Instantiations of class template @c inversive_congruential_engine model a
0038  * \pseudo_random_number_generator. It uses the inversive congruential
0039  * algorithm (ICG) described in
0040  *
0041  *  @blockquote
0042  *  "Inversive pseudorandom number generators: concepts, results and links",
0043  *  Peter Hellekalek, In: "Proceedings of the 1995 Winter Simulation
0044  *  Conference", C. Alexopoulos, K. Kang, W.R. Lilegdon, and D. Goldsman
0045  *  (editors), 1995, pp. 255-262. ftp://random.mat.sbg.ac.at/pub/data/wsc95.ps
0046  *  @endblockquote
0047  *
0048  * The output sequence is defined by x(n+1) = (a*inv(x(n)) - b) (mod p),
0049  * where x(0), a, b, and the prime number p are parameters of the generator.
0050  * The expression inv(k) denotes the multiplicative inverse of k in the
0051  * field of integer numbers modulo p, with inv(0) := 0.
0052  *
0053  * The template parameter IntType shall denote a signed integral type large
0054  * enough to hold p; a, b, and p are the parameters of the generators. The
0055  * template parameter val is the validation value checked by validation.
0056  *
0057  * @xmlnote
0058  * The implementation currently uses the Euclidian Algorithm to compute
0059  * the multiplicative inverse. Therefore, the inversive generators are about
0060  * 10-20 times slower than the others (see section"performance"). However,
0061  * the paper talks of only 3x slowdown, so the Euclidian Algorithm is probably
0062  * not optimal for calculating the multiplicative inverse.
0063  * @endxmlnote
0064  */
0065 template<class IntType, IntType a, IntType b, IntType p>
0066 class inversive_congruential_engine
0067 {
0068 public:
0069     typedef IntType result_type;
0070     BOOST_STATIC_CONSTANT(bool, has_fixed_range = false);
0071
0072     BOOST_STATIC_CONSTANT(result_type, multiplier = a);
0073     BOOST_STATIC_CONSTANT(result_type, increment = b);
0074     BOOST_STATIC_CONSTANT(result_type, modulus = p);
0075     BOOST_STATIC_CONSTANT(IntType, default_seed = 1);
0076
0077     static BOOST_CONSTEXPR result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () { return b == 0 ? 1 : 0; }
0078     static BOOST_CONSTEXPR result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () { return p-1; }
0079
0080     /**
0081      * Constructs an @c inversive_congruential_engine, seeding it with
0082      * the default seed.
0083      */
0084     inversive_congruential_engine() { seed(); }
0085
0086     /**
0087      * Constructs an @c inversive_congruential_engine, seeding it with @c x0.
0088      */
0089     BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(inversive_congruential_engine,
0090                                                IntType, x0)
0091     { seed(x0); }
0092
0093     /**
0094      * Constructs an @c inversive_congruential_engine, seeding it with values
0095      * produced by a call to @c seq.generate().
0096      */
0097     BOOST_RANDOM_DETAIL_SEED_SEQ_CONSTRUCTOR(inversive_congruential_engine,
0098                                              SeedSeq, seq)
0099     { seed(seq); }
0100
0101     /**
0102      * Constructs an @c inversive_congruential_engine, seeds it
0103      * with values taken from the itrator range [first, last),
0104      * and adjusts first to point to the element after the last one
0105      * used.  If there are not enough elements, throws @c std::invalid_argument.
0106      *
0107      * first and last must be input iterators.
0108      */
0109     template<class It> inversive_congruential_engine(It& first, It last)
0110     { seed(first, last); }
0111
0112     /**
0113      * Calls seed(default_seed)
0114      */
0115     void seed() { seed(default_seed); }
0116
0117     /**
0118      * If c mod m is zero and x0 mod m is zero, changes the current value of
0119      * the generator to 1. Otherwise, changes it to x0 mod m. If c is zero,
0120      * distinct seeds in the range [1,m) will leave the generator in distinct
0121      * states. If c is not zero, the range is [0,m).
0122      */
0123     BOOST_RANDOM_DETAIL_ARITHMETIC_SEED(inversive_congruential_engine, IntType, x0)
0124     {
0125         // wrap _x if it doesn't fit in the destination
0126         if(modulus == 0) {
0127             _value = x0;
0128         } else {
0129             _value = x0 % modulus;
0130         }
0131         // handle negative seeds
0132         if(_value < 0) {
0133             _value += modulus;
0134         }
0135         // adjust to the correct range
0136         if(increment == 0 && _value == 0) {
0137             _value = 1;
0138         }
0139         BOOST_ASSERT(_value >= (min)());
0140         BOOST_ASSERT(_value <= (max)());
0141     }
0142
0143     /**
0144      * Seeds an @c inversive_congruential_engine using values from a SeedSeq.
0145      */
0146     BOOST_RANDOM_DETAIL_SEED_SEQ_SEED(inversive_congruential_engine, SeedSeq, seq)
0147     { seed(detail::seed_one_int<IntType, modulus>(seq)); }
0148
0149     /**
0150      * seeds an @c inversive_congruential_engine with values taken
0151      * from the itrator range [first, last) and adjusts @c first to
0152      * point to the element after the last one used.  If there are
0153      * not enough elements, throws @c std::invalid_argument.
0154      *
0155      * @c first and @c last must be input iterators.
0156      */
0157     template<class It> void seed(It& first, It last)
0158     { seed(detail::get_one_int<IntType, modulus>(first, last)); }
0159
0160     /** Returns the next output of the generator. */
0161     IntType operator()()
0162     {
0163         typedef const_mod<IntType, p> do_mod;
0164         _value = do_mod::mult_add(a, do_mod::invert(_value), b);
0165         return _value;
0166     }
0167
0168     /** Fills a range with random values */
0169     template<class Iter>
0170     void generate(Iter first, Iter last)
0171     { detail::generate_from_int(*this, first, last); }
0172
0173     /** Advances the state of the generator by @c z. */
0174     void discard(boost::uintmax_t z)
0175     {
0176         for(boost::uintmax_t j = 0; j < z; ++j) {
0177             (*this)();
0178         }
0179     }
0180
0181     /**
0182      * Writes the textual representation of the generator to a @c std::ostream.
0183      */
0184     BOOST_RANDOM_DETAIL_OSTREAM_OPERATOR(os, inversive_congruential_engine, x)
0185     {
0186         os << x._value;
0187         return os;
0188     }
0189
0190     /**
0191      * Reads the textual representation of the generator from a @c std::istream.
0192      */
0193     BOOST_RANDOM_DETAIL_ISTREAM_OPERATOR(is, inversive_congruential_engine, x)
0194     {
0195         is >> x._value;
0196         return is;
0197     }
0198
0199     /**
0200      * Returns true if the two generators will produce identical
0201      * sequences of outputs.
0202      */
0203     BOOST_RANDOM_DETAIL_EQUALITY_OPERATOR(inversive_congruential_engine, x, y)
0204     { return x._value == y._value; }
0205
0206     /**
0207      * Returns true if the two generators will produce different
0208      * sequences of outputs.
0209      */
0210     BOOST_RANDOM_DETAIL_INEQUALITY_OPERATOR(inversive_congruential_engine)
0211
0212 private:
0213     IntType _value;
0214 };
0215
0216 #ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION
0217 //  A definition is required even for integral static constants
0218 template<class IntType, IntType a, IntType b, IntType p>
0219 const bool inversive_congruential_engine<IntType, a, b, p>::has_fixed_range;
0220 template<class IntType, IntType a, IntType b, IntType p>
0221 const typename inversive_congruential_engine<IntType, a, b, p>::result_type inversive_congruential_engine<IntType, a, b, p>::multiplier;
0222 template<class IntType, IntType a, IntType b, IntType p>
0223 const typename inversive_congruential_engine<IntType, a, b, p>::result_type inversive_congruential_engine<IntType, a, b, p>::increment;
0224 template<class IntType, IntType a, IntType b, IntType p>
0225 const typename inversive_congruential_engine<IntType, a, b, p>::result_type inversive_congruential_engine<IntType, a, b, p>::modulus;
0226 template<class IntType, IntType a, IntType b, IntType p>
0227 const typename inversive_congruential_engine<IntType, a, b, p>::result_type inversive_congruential_engine<IntType, a, b, p>::default_seed;
0228 #endif
0229
0230 /// \cond show_deprecated
0231
0232 // provided for backwards compatibility
0233 template<class IntType, IntType a, IntType b, IntType p, IntType val = 0>
0234 class inversive_congruential : public inversive_congruential_engine<IntType, a, b, p>
0235 {
0236     typedef inversive_congruential_engine<IntType, a, b, p> base_type;
0237 public:
0238     inversive_congruential(IntType x0 = 1) : base_type(x0) {}
0239     template<class It>
0240     inversive_congruential(It& first, It last) : base_type(first, last) {}
0241 };
0242
0243 /// \endcond
0244
0245 /**
0246  * The specialization hellekalek1995 was suggested in
0247  *
0248  *  @blockquote
0249  *  "Inversive pseudorandom number generators: concepts, results and links",
0250  *  Peter Hellekalek, In: "Proceedings of the 1995 Winter Simulation
0251  *  Conference", C. Alexopoulos, K. Kang, W.R. Lilegdon, and D. Goldsman
0252  *  (editors), 1995, pp. 255-262. ftp://random.mat.sbg.ac.at/pub/data/wsc95.ps
0253  *  @endblockquote
0254  */
0255 typedef inversive_congruential_engine<uint32_t, 9102, 2147483647-36884165,
0256   2147483647> hellekalek1995;
0257
0258 } // namespace random
0259
0260 using random::hellekalek1995;
0261
0262 } // namespace boost
0263
0264 #include <boost/random/detail/enable_warnings.hpp>
0265
0266 #endif // BOOST_RANDOM_INVERSIVE_CONGRUENTIAL_HPP