boost/random/linear_feedback_shift.hpp

0001 /* boost random/linear_feedback_shift.hpp header file
0002  *
0003  * Copyright Jens Maurer 2002
0004  * Copyright Steven Watanabe 2011
0005  * Distributed under the Boost Software License, Version 1.0. (See
0006  * accompanying file LICENSE_1_0.txt or copy at
0007  * http://www.boost.org/LICENSE_1_0.txt)
0008  *
0009  * See http://www.boost.org for most recent version including documentation.
0010  *
0011  * $Id$
0012  *
0013  */
0014
0015 #ifndef BOOST_RANDOM_LINEAR_FEEDBACK_SHIFT_HPP
0016 #define BOOST_RANDOM_LINEAR_FEEDBACK_SHIFT_HPP
0017
0018 #include <iosfwd>
0019 #include <stdexcept>
0020 #include <boost/config.hpp>
0021 #include <boost/cstdint.hpp>
0022 #include <boost/static_assert.hpp>
0023 #include <boost/integer/integer_mask.hpp>
0024 #include <boost/random/detail/config.hpp>
0025 #include <boost/random/detail/seed.hpp>
0026 #include <boost/random/detail/operators.hpp>
0027 #include <boost/random/detail/seed_impl.hpp>
0028
0029 namespace boost {
0030 namespace random {
0031
0032 /**
0033  * Instatiations of @c linear_feedback_shift model a
0034  * \pseudo_random_number_generator.  It was originally
0035  * proposed in
0036  *
0037  *  @blockquote
0038  *  "Random numbers generated by linear recurrence modulo two.",
0039  *  Tausworthe, R. C.(1965), Mathematics of Computation 19, 201-209.
0040  *  @endblockquote
0041  */
0042 template<class UIntType, int w, int k, int q, int s>
0043 class linear_feedback_shift_engine
0044 {
0045 public:
0046     typedef UIntType result_type;
0047     BOOST_STATIC_CONSTANT(bool, has_fixed_range = false);
0048     BOOST_STATIC_CONSTANT(int, word_size = w);
0049     BOOST_STATIC_CONSTANT(int, exponent1 = k);
0050     BOOST_STATIC_CONSTANT(int, exponent2 = q);
0051     BOOST_STATIC_CONSTANT(int, step_size = s);
0052     BOOST_STATIC_CONSTANT(UIntType, default_seed = 341);
0053
0054     /** Returns the smallest value that the generator can produce. */
0055     static BOOST_CONSTEXPR result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () { return 0; }
0056     /** Returns the largest value that the generator can produce. */
0057     static BOOST_CONSTEXPR result_type max BOOST_PREVENT_MACRO_SUBSTITUTION ()
0058     { return wordmask(); }
0059
0060     BOOST_STATIC_ASSERT(w > 0);
0061     BOOST_STATIC_ASSERT(q > 0);
0062     BOOST_STATIC_ASSERT(k < w);
0063     BOOST_STATIC_ASSERT(0 < 2*q && 2*q < k);
0064     BOOST_STATIC_ASSERT(0 < s && s <= k-q);
0065
0066     /** Constructs a @c linear_feedback_shift_engine, using the default seed. */
0067     linear_feedback_shift_engine() { seed(); }
0068
0069     /** Constructs a @c linear_feedback_shift_engine, seeding it with s0. */
0070     BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(linear_feedback_shift_engine,
0071         UIntType, s0)
0072     { seed(s0); }
0073
0074     /** Constructs a @c linear_feedback_shift_engine, seeding it with seq. */
0075     BOOST_RANDOM_DETAIL_SEED_SEQ_CONSTRUCTOR(linear_feedback_shift_engine,
0076         SeedSeq, seq)
0077     { seed(seq); }
0078
0079     /**
0080      * Constructs a @c linear_feedback_shift_engine, seeding it with
0081      * values from the range [first, last).
0082      */
0083     template<class It> linear_feedback_shift_engine(It& first, It last)
0084     { seed(first, last); }
0085
0086     /** Seeds a @c linear_feedback_shift_engine with the default seed. */
0087     void seed() {  seed(default_seed); }
0088
0089     /** Seeds a @c linear_feedback_shift_engine with @c s0. */
0090     BOOST_RANDOM_DETAIL_ARITHMETIC_SEED(linear_feedback_shift_engine,
0091         UIntType, s0)
0092     {
0093         value = s0 & wordmask();
0094         if(value < (1 << (w-k))) {
0095             value += 1 << (w-k);
0096         }
0097     }
0098
0099     /**
0100      * Seeds a @c linear_feedback_shift_engine with values
0101      * produced by @c seq.generate().
0102      */
0103     BOOST_RANDOM_DETAIL_SEED_SEQ_SEED(linear_feedback_shift_engine,
0104         SeedSeq, seq)
0105     { seed(detail::seed_one_int<UIntType, (UIntType(2) << (w - 1))>(seq)); }
0106
0107     /**
0108      * Seeds a @c linear_feedback_shift_engine with values
0109      * from the range [first, last).
0110      */
0111     template<class It> void seed(It& first, It last)
0112     {
0113         seed(detail::get_one_int<UIntType, (UIntType(2) << (w - 1))>(first, last));
0114     }
0115
0116     /** Returns the next value of the generator. */
0117     result_type operator()()
0118     {
0119         const UIntType b = (((value << q) ^ value) & wordmask()) >> (k-s);
0120         const UIntType mask = (wordmask() << (w-k)) & wordmask();
0121         value = ((value & mask) << s) ^ b;
0122         return value;
0123     }
0124
0125     /** Fills a range with random values */
0126     template<class Iter>
0127     void generate(Iter first, Iter last)
0128     { detail::generate_from_int(*this, first, last); }
0129
0130     /** Advances the state of the generator by @c z. */
0131     void discard(boost::uintmax_t z)
0132     {
0133         for(boost::uintmax_t j = 0; j < z; ++j) {
0134             (*this)();
0135         }
0136     }
0137
0138     /**
0139      * Writes the textual representation of the generator to a @c std::ostream.
0140      */
0141     BOOST_RANDOM_DETAIL_OSTREAM_OPERATOR(os, linear_feedback_shift_engine, x)
0142     {
0143         os << x.value;
0144         return os;
0145     }
0146
0147     /**
0148      * Reads the textual representation of the generator from a @c std::istream.
0149      */
0150     BOOST_RANDOM_DETAIL_ISTREAM_OPERATOR(is, linear_feedback_shift_engine, x)
0151     {
0152         is >> x.value;
0153         return is;
0154     }
0155
0156     /**
0157      * Returns true if the two generators will produce identical
0158      * sequences of outputs.
0159      */
0160     BOOST_RANDOM_DETAIL_EQUALITY_OPERATOR(linear_feedback_shift_engine, x, y)
0161     { return x.value == y.value; }
0162
0163     /**
0164      * Returns true if the two generators will produce different
0165      * sequences of outputs.
0166      */
0167     BOOST_RANDOM_DETAIL_INEQUALITY_OPERATOR(linear_feedback_shift_engine)
0168
0169 private:
0170     /// \cond show_private
0171     static BOOST_CONSTEXPR UIntType wordmask() { return boost::low_bits_mask_t<w>::sig_bits; }
0172     /// \endcond
0173     UIntType value;
0174 };
0175
0176 #ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION
0177 //  A definition is required even for integral static constants
0178 template<class UIntType, int w, int k, int q, int s>
0179 const bool linear_feedback_shift_engine<UIntType, w, k, q, s>::has_fixed_range;
0180 template<class UIntType, int w, int k, int q, int s>
0181 const int linear_feedback_shift_engine<UIntType, w, k, q, s>::word_size;
0182 template<class UIntType, int w, int k, int q, int s>
0183 const int linear_feedback_shift_engine<UIntType, w, k, q, s>::exponent1;
0184 template<class UIntType, int w, int k, int q, int s>
0185 const int linear_feedback_shift_engine<UIntType, w, k, q, s>::exponent2;
0186 template<class UIntType, int w, int k, int q, int s>
0187 const int linear_feedback_shift_engine<UIntType, w, k, q, s>::step_size;
0188 template<class UIntType, int w, int k, int q, int s>
0189 const UIntType linear_feedback_shift_engine<UIntType, w, k, q, s>::default_seed;
0190 #endif
0191
0192 /// \cond show_deprecated
0193
0194 /** Provided for backwards compatibility. */
0195 template<class UIntType, int w, int k, int q, int s, UIntType v = 0>
0196 class linear_feedback_shift :
0197     public linear_feedback_shift_engine<UIntType, w, k, q, s>
0198 {
0199     typedef linear_feedback_shift_engine<UIntType, w, k, q, s> base_type;
0200 public:
0201     linear_feedback_shift() {}
0202     BOOST_RANDOM_DETAIL_SEED_SEQ_CONSTRUCTOR(linear_feedback_shift,
0203         SeedSeq, seq)
0204     { seed(seq); }
0205     BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(linear_feedback_shift,
0206         UIntType, val)
0207     { seed(val); }
0208     template<class It>
0209     linear_feedback_shift(It& first, It last) : base_type(first, last) {}
0210 };
0211
0212 /// \endcond
0213
0214 } // namespace random
0215 } // namespace boost
0216
0217 #endif // BOOST_RANDOM_LINEAR_FEEDBACK_SHIFT_HPP