boost/random/linear_feedback_shift.hpp

   1 /* boost random/linear_feedback_shift.hpp header file
   2  *
   3  * Copyright Jens Maurer 2002
   4  * Copyright Steven Watanabe 2011
   5  * Distributed under the Boost Software License, Version 1.0. (See
   6  * accompanying file LICENSE_1_0.txt or copy at
   7  * http://www.boost.org/LICENSE_1_0.txt)
   8  *
   9  * See http://www.boost.org for most recent version including documentation.
  10  *
  11  * $Id: linear_feedback_shift.hpp 71018 2011-04-05 21:27:52Z steven_watanabe $
  12  *
  13  */
  14
  15 #ifndef BOOST_RANDOM_LINEAR_FEEDBACK_SHIFT_HPP
  16 #define BOOST_RANDOM_LINEAR_FEEDBACK_SHIFT_HPP
  17
  18 #include <iosfwd>
  19 #include <stdexcept>
  20 #include <boost/config.hpp>
  21 #include <boost/cstdint.hpp>
  22 #include <boost/static_assert.hpp>
  23 #include <boost/integer/integer_mask.hpp>
  24 #include <boost/random/detail/config.hpp>
  25 #include <boost/random/detail/seed.hpp>
  26 #include <boost/random/detail/operators.hpp>
  27 #include <boost/random/detail/seed_impl.hpp>
  28
  29 namespace boost {
  30 namespace random {
  31
  32 /**
  33  * Instatiations of @c linear_feedback_shift model a
  34  * \pseudo_random_number_generator.  It was originally
  35  * proposed in
  36  *
  37  *  @blockquote
  38  *  "Random numbers generated by linear recurrence modulo two.",
  39  *  Tausworthe, R. C.(1965), Mathematics of Computation 19, 201-209.
  40  *  @endblockquote
  41  */
  42 template<class UIntType, int w, int k, int q, int s>
  43 class linear_feedback_shift_engine
  44 {
  45 public:
  46     typedef UIntType result_type;
  47     BOOST_STATIC_CONSTANT(bool, has_fixed_range = false);
  48     BOOST_STATIC_CONSTANT(int, word_size = w);
  49     BOOST_STATIC_CONSTANT(int, exponent1 = k);
  50     BOOST_STATIC_CONSTANT(int, exponent2 = q);
  51     BOOST_STATIC_CONSTANT(int, step_size = s);
  52     BOOST_STATIC_CONSTANT(UIntType, default_seed = 341);
  53
  54     /** Returns the smallest value that the generator can produce. */
  55     static result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () { return 0; }
  56     /** Returns the largest value that the generator can produce. */
  57     static result_type max BOOST_PREVENT_MACRO_SUBSTITUTION ()
  58     { return wordmask(); }
  59
  60     BOOST_STATIC_ASSERT(w > 0);
  61     BOOST_STATIC_ASSERT(q > 0);
  62     BOOST_STATIC_ASSERT(k < w);
  63     BOOST_STATIC_ASSERT(0 < 2*q && 2*q < k);
  64     BOOST_STATIC_ASSERT(0 < s && s <= k-q);
  65
  66     /** Constructs a @c linear_feedback_shift_engine, using the default seed. */
  67     linear_feedback_shift_engine() { seed(); }
  68
  69     /** Constructs a @c linear_feedback_shift_engine, seeding it with s0. */
  70     BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(linear_feedback_shift_engine,
  71         UIntType, s0)
  72     { seed(s0); }
  73
  74     /** Constructs a @c linear_feedback_shift_engine, seeding it with seq. */
  75     BOOST_RANDOM_DETAIL_SEED_SEQ_CONSTRUCTOR(linear_feedback_shift_engine,
  76         SeedSeq, seq)
  77     { seed(seq); }
  78
  79     /**
  80      * Constructs a @c linear_feedback_shift_engine, seeding it with
  81      * values from the range [first, last).
  82      */
  83     template<class It> linear_feedback_shift_engine(It& first, It last)
  84     { seed(first, last); }
  85
  86     /** Seeds a @c linear_feedback_shift_engine with the default seed. */
  87     void seed() {  seed(default_seed); }
  88
  89     /** Seeds a @c linear_feedback_shift_engine with @c s0. */
  90     BOOST_RANDOM_DETAIL_ARITHMETIC_SEED(linear_feedback_shift_engine,
  91         UIntType, s0)
  92     {
  93         value = s0 & wordmask();
  94         if(value < (1 << (w-k))) {
  95             value += 1 << (w-k);
  96         }
  97     }
  98
  99     /**
 100      * Seeds a @c linear_feedback_shift_engine with values
 101      * produced by @c seq.generate().
 102      */
 103     BOOST_RANDOM_DETAIL_SEED_SEQ_SEED(linear_feedback_shift_engine,
 104         SeedSeq, seq)
 105     { seed(detail::seed_one_int<UIntType, (UIntType(2) << (w - 1))>(seq)); }
 106
 107     /**
 108      * Seeds a @c linear_feedback_shift_engine with values
 109      * from the range [first, last).
 110      */
 111     template<class It> void seed(It& first, It last)
 112     {
 113         seed(detail::get_one_int<UIntType, (UIntType(2) << (w - 1))>(first, last));
 114     }
 115
 116     /** Returns the next value of the generator. */
 117     result_type operator()()
 118     {
 119         const UIntType b = (((value << q) ^ value) & wordmask()) >> (k-s);
 120         const UIntType mask = (wordmask() << (w-k)) & wordmask();
 121         value = ((value & mask) << s) ^ b;
 122         return value;
 123     }
 124
 125     /** Fills a range with random values */
 126     template<class Iter>
 127     void generate(Iter first, Iter last)
 128     { detail::generate_from_int(*this, first, last); }
 129
 130     /** Advances the state of the generator by @c z. */
 131     void discard(boost::uintmax_t z)
 132     {
 133         for(boost::uintmax_t j = 0; j < z; ++j) {
 134             (*this)();
 135         }
 136     }
 137
 138     /**
 139      * Writes the textual representation of the generator to a @c std::ostream.
 140      */
 141     BOOST_RANDOM_DETAIL_OSTREAM_OPERATOR(os, linear_feedback_shift_engine, x)
 142     {
 143         os << x.value;
 144         return os;
 145     }
 146
 147     /**
 148      * Reads the textual representation of the generator from a @c std::istream.
 149      */
 150     BOOST_RANDOM_DETAIL_ISTREAM_OPERATOR(is, linear_feedback_shift_engine, x)
 151     {
 152         is >> x.value;
 153         return is;
 154     }
 155
 156     /**
 157      * Returns true if the two generators will produce identical
 158      * sequences of outputs.
 159      */
 160     BOOST_RANDOM_DETAIL_EQUALITY_OPERATOR(linear_feedback_shift_engine, x, y)
 161     { return x.value == y.value; }
 162
 163     /**
 164      * Returns true if the two generators will produce different
 165      * sequences of outputs.
 166      */
 167     BOOST_RANDOM_DETAIL_INEQUALITY_OPERATOR(linear_feedback_shift_engine)
 168
 169 private:
 170     /// \cond show_private
 171     static UIntType wordmask() { return boost::low_bits_mask_t<w>::sig_bits; }
 172     /// \endcond
 173     UIntType value;
 174 };
 175
 176 #ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION
 177 //  A definition is required even for integral static constants
 178 template<class UIntType, int w, int k, int q, int s>
 179 const bool linear_feedback_shift_engine<UIntType, w, k, q, s>::has_fixed_range;
 180 template<class UIntType, int w, int k, int q, int s>
 181 const int linear_feedback_shift_engine<UIntType, w, k, q, s>::word_size;
 182 template<class UIntType, int w, int k, int q, int s>
 183 const int linear_feedback_shift_engine<UIntType, w, k, q, s>::exponent1;
 184 template<class UIntType, int w, int k, int q, int s>
 185 const int linear_feedback_shift_engine<UIntType, w, k, q, s>::exponent2;
 186 template<class UIntType, int w, int k, int q, int s>
 187 const int linear_feedback_shift_engine<UIntType, w, k, q, s>::step_size;
 188 template<class UIntType, int w, int k, int q, int s>
 189 const UIntType linear_feedback_shift_engine<UIntType, w, k, q, s>::default_seed;
 190 #endif
 191
 192 /// \cond show_deprecated
 193
 194 /** Provided for backwards compatibility. */
 195 template<class UIntType, int w, int k, int q, int s, UIntType v = 0>
 196 class linear_feedback_shift :
 197     public linear_feedback_shift_engine<UIntType, w, k, q, s>
 198 {
 199     typedef linear_feedback_shift_engine<UIntType, w, k, q, s> base_type;
 200 public:
 201     linear_feedback_shift() {}
 202     BOOST_RANDOM_DETAIL_SEED_SEQ_CONSTRUCTOR(linear_feedback_shift,
 203         SeedSeq, seq)
 204     { seed(seq); }
 205     BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(linear_feedback_shift,
 206         UIntType, val)
 207     { seed(val); }
 208     template<class It>
 209     linear_feedback_shift(It& first, It last) : base_type(first, last) {}
 210 };
 211
 212 /// \endcond
 213
 214 } // namespace random
 215 } // namespace boost
 216
 217 #endif // BOOST_RANDOM_LINEAR_FEEDBACK_SHIFT_HPP