boost/random/mersenne_twister.hpp

   1 /* boost random/mersenne_twister.hpp header file
   2  *
   3  * Copyright Jens Maurer 2000-2001
   4  * Distributed under the Boost Software License, Version 1.0. (See
   5  * accompanying file LICENSE_1_0.txt or copy at
   6  * http://www.boost.org/LICENSE_1_0.txt)
   7  *
   8  * See http://www.boost.org for most recent version including documentation.
   9  *
  10  * $Id: mersenne_twister.hpp 60755 2010-03-22 00:45:06Z steven_watanabe $
  11  *
  12  * Revision history
  13  *  2001-02-18  moved to individual header files
  14  */
  15
  16 #ifndef BOOST_RANDOM_MERSENNE_TWISTER_HPP
  17 #define BOOST_RANDOM_MERSENNE_TWISTER_HPP
  18
  19 #include <iostream>
  20 #include <algorithm>     // std::copy
  21 #include <stdexcept>
  22 #include <boost/config.hpp>
  23 #include <boost/limits.hpp>
  24 #include <boost/static_assert.hpp>
  25 #include <boost/integer_traits.hpp>
  26 #include <boost/cstdint.hpp>
  27 #include <boost/random/linear_congruential.hpp>
  28 #include <boost/detail/workaround.hpp>
  29 #include <boost/random/detail/config.hpp>
  30 #include <boost/random/detail/ptr_helper.hpp>
  31 #include <boost/random/detail/seed.hpp>
  32
  33 namespace boost {
  34 namespace random {
  35
  36 /**
  37  * Instantiations of class template mersenne_twister model a
  38  * \pseudo_random_number_generator. It uses the algorithm described in
  39  *
  40  *  @blockquote
  41  *  "Mersenne Twister: A 623-dimensionally equidistributed uniform
  42  *  pseudo-random number generator", Makoto Matsumoto and Takuji Nishimura,
  43  *  ACM Transactions on Modeling and Computer Simulation: Special Issue on
  44  *  Uniform Random Number Generation, Vol. 8, No. 1, January 1998, pp. 3-30.
  45  *  @endblockquote
  46  *
  47  * @xmlnote
  48  * The boost variant has been implemented from scratch and does not
  49  * derive from or use mt19937.c provided on the above WWW site. However, it
  50  * was verified that both produce identical output.
  51  * @endxmlnote
  52  *
  53  * The seeding from an integer was changed in April 2005 to address a
  54  * <a href="http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/emt19937ar.html">weakness</a>.
  55  *
  56  * The quality of the generator crucially depends on the choice of the
  57  * parameters.  User code should employ one of the sensibly parameterized
  58  * generators such as \mt19937 instead.
  59  *
  60  * The generator requires considerable amounts of memory for the storage of
  61  * its state array. For example, \mt11213b requires about 1408 bytes and
  62  * \mt19937 requires about 2496 bytes.
  63  */
  64 template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
  65   int s, UIntType b, int t, UIntType c, int l, UIntType val>
  66 class mersenne_twister
  67 {
  68 public:
  69   typedef UIntType result_type;
  70   BOOST_STATIC_CONSTANT(int, word_size = w);
  71   BOOST_STATIC_CONSTANT(int, state_size = n);
  72   BOOST_STATIC_CONSTANT(int, shift_size = m);
  73   BOOST_STATIC_CONSTANT(int, mask_bits = r);
  74   BOOST_STATIC_CONSTANT(UIntType, parameter_a = a);
  75   BOOST_STATIC_CONSTANT(int, output_u = u);
  76   BOOST_STATIC_CONSTANT(int, output_s = s);
  77   BOOST_STATIC_CONSTANT(UIntType, output_b = b);
  78   BOOST_STATIC_CONSTANT(int, output_t = t);
  79   BOOST_STATIC_CONSTANT(UIntType, output_c = c);
  80   BOOST_STATIC_CONSTANT(int, output_l = l);
  81
  82   BOOST_STATIC_CONSTANT(bool, has_fixed_range = false);
  83
  84   /**
  85    * Constructs a @c mersenne_twister and calls @c seed().
  86    */
  87   mersenne_twister() { seed(); }
  88
  89   /**
  90    * Constructs a @c mersenne_twister and calls @c seed(value).
  91    */
  92   BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(mersenne_twister, UIntType, value)
  93   { seed(value); }
  94   template<class It> mersenne_twister(It& first, It last) { seed(first,last); }
  95
  96   /**
  97    * Constructs a mersenne_twister and calls @c seed(gen).
  98    *
  99    * @xmlnote
 100    * The copy constructor will always be preferred over
 101    * the templated constructor.
 102    * @endxmlnote
 103    */
 104   BOOST_RANDOM_DETAIL_GENERATOR_CONSTRUCTOR(mersenne_twister, Generator, gen)
 105   { seed(gen); }
 106
 107   // compiler-generated copy ctor and assignment operator are fine
 108
 109   /** Calls @c seed(result_type(5489)). */
 110   void seed() { seed(UIntType(5489)); }
 111
 112   /**
 113    * Sets the state x(0) to v mod 2w. Then, iteratively,
 114    * sets x(i) to (i + 1812433253 * (x(i-1) xor (x(i-1) rshift w-2))) mod 2<sup>w</sup>
 115    * for i = 1 .. n-1. x(n) is the first value to be returned by operator().
 116    */
 117   BOOST_RANDOM_DETAIL_ARITHMETIC_SEED(mersenne_twister, UIntType, value)
 118   {
 119     // New seeding algorithm from
 120     // http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/emt19937ar.html
 121     // In the previous versions, MSBs of the seed affected only MSBs of the
 122     // state x[].
 123     const UIntType mask = ~0u;
 124     x[0] = value & mask;
 125     for (i = 1; i < n; i++) {
 126       // See Knuth "The Art of Computer Programming" Vol. 2, 3rd ed., page 106
 127       x[i] = (1812433253UL * (x[i-1] ^ (x[i-1] >> (w-2))) + i) & mask;
 128     }
 129   }
 130
 131   /**
 132    * Sets the state of this mersenne_twister to the values
 133    * returned by n invocations of gen.
 134    *
 135    * Complexity: Exactly n invocations of gen.
 136    */
 137   BOOST_RANDOM_DETAIL_GENERATOR_SEED(mersenne_twister, Generator, gen)
 138   {
 139 #ifndef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS
 140     BOOST_STATIC_ASSERT(!std::numeric_limits<result_type>::is_signed);
 141 #endif
 142     // I could have used std::generate_n, but it takes "gen" by value
 143     for(int j = 0; j < n; j++)
 144       x[j] = gen();
 145     i = n;
 146   }
 147
 148   template<class It>
 149   void seed(It& first, It last)
 150   {
 151     int j;
 152     for(j = 0; j < n && first != last; ++j, ++first)
 153       x[j] = *first;
 154     i = n;
 155     if(first == last && j < n)
 156       throw std::invalid_argument("mersenne_twister::seed");
 157   }
 158
 159   result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return 0; }
 160   result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const
 161   {
 162     // avoid "left shift count >= with of type" warning
 163     result_type res = 0;
 164     for(int j = 0; j < w; ++j)
 165       res |= (1u << j);
 166     return res;
 167   }
 168
 169   result_type operator()();
 170   static bool validation(result_type v) { return val == v; }
 171
 172 #ifndef BOOST_NO_OPERATORS_IN_NAMESPACE
 173
 174 #ifndef BOOST_RANDOM_NO_STREAM_OPERATORS
 175   template<class CharT, class Traits>
 176   friend std::basic_ostream<CharT,Traits>&
 177   operator<<(std::basic_ostream<CharT,Traits>& os, const mersenne_twister& mt)
 178   {
 179     for(int j = 0; j < mt.state_size; ++j)
 180       os << mt.compute(j) << " ";
 181     return os;
 182   }
 183
 184   template<class CharT, class Traits>
 185   friend std::basic_istream<CharT,Traits>&
 186   operator>>(std::basic_istream<CharT,Traits>& is, mersenne_twister& mt)
 187   {
 188     for(int j = 0; j < mt.state_size; ++j)
 189       is >> mt.x[j] >> std::ws;
 190     // MSVC (up to 7.1) and Borland (up to 5.64) don't handle the template
 191     // value parameter "n" available from the class template scope, so use
 192     // the static constant with the same value
 193     mt.i = mt.state_size;
 194     return is;
 195   }
 196 #endif
 197
 198   friend bool operator==(const mersenne_twister& x, const mersenne_twister& y)
 199   {
 200     for(int j = 0; j < state_size; ++j)
 201       if(x.compute(j) != y.compute(j))
 202         return false;
 203     return true;
 204   }
 205
 206   friend bool operator!=(const mersenne_twister& x, const mersenne_twister& y)
 207   { return !(x == y); }
 208 #else
 209   // Use a member function; Streamable concept not supported.
 210   bool operator==(const mersenne_twister& rhs) const
 211   {
 212     for(int j = 0; j < state_size; ++j)
 213       if(compute(j) != rhs.compute(j))
 214         return false;
 215     return true;
 216   }
 217
 218   bool operator!=(const mersenne_twister& rhs) const
 219   { return !(*this == rhs); }
 220 #endif
 221
 222 private:
 223   /// \cond hide_private_members
 224   // returns x(i-n+index), where index is in 0..n-1
 225   UIntType compute(unsigned int index) const
 226   {
 227     // equivalent to (i-n+index) % 2n, but doesn't produce negative numbers
 228     return x[ (i + n + index) % (2*n) ];
 229   }
 230   void twist(int block);
 231   /// \endcond
 232
 233   // state representation: next output is o(x(i))
 234   //   x[0]  ... x[k] x[k+1] ... x[n-1]     x[n]     ... x[2*n-1]   represents
 235   //  x(i-k) ... x(i) x(i+1) ... x(i-k+n-1) x(i-k-n) ... x[i(i-k-1)]
 236   // The goal is to always have x(i-n) ... x(i-1) available for
 237   // operator== and save/restore.
 238
 239   UIntType x[2*n];
 240   int i;
 241 };
 242
 243 #ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION
 244 //  A definition is required even for integral static constants
 245 template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
 246   int s, UIntType b, int t, UIntType c, int l, UIntType val>
 247 const bool mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::has_fixed_range;
 248 template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
 249   int s, UIntType b, int t, UIntType c, int l, UIntType val>
 250 const int mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::state_size;
 251 template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
 252   int s, UIntType b, int t, UIntType c, int l, UIntType val>
 253 const int mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::shift_size;
 254 template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
 255   int s, UIntType b, int t, UIntType c, int l, UIntType val>
 256 const int mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::mask_bits;
 257 template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
 258   int s, UIntType b, int t, UIntType c, int l, UIntType val>
 259 const UIntType mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::parameter_a;
 260 template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
 261   int s, UIntType b, int t, UIntType c, int l, UIntType val>
 262 const int mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::output_u;
 263 template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
 264   int s, UIntType b, int t, UIntType c, int l, UIntType val>
 265 const int mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::output_s;
 266 template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
 267   int s, UIntType b, int t, UIntType c, int l, UIntType val>
 268 const UIntType mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::output_b;
 269 template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
 270   int s, UIntType b, int t, UIntType c, int l, UIntType val>
 271 const int mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::output_t;
 272 template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
 273   int s, UIntType b, int t, UIntType c, int l, UIntType val>
 274 const UIntType mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::output_c;
 275 template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
 276   int s, UIntType b, int t, UIntType c, int l, UIntType val>
 277 const int mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::output_l;
 278 #endif
 279
 280 /// \cond hide_private_members
 281 template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
 282   int s, UIntType b, int t, UIntType c, int l, UIntType val>
 283 void mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::twist(int block)
 284 {
 285   const UIntType upper_mask = (~0u) << r;
 286   const UIntType lower_mask = ~upper_mask;
 287
 288   if(block == 0) {
 289     for(int j = n; j < 2*n; j++) {
 290       UIntType y = (x[j-n] & upper_mask) | (x[j-(n-1)] & lower_mask);
 291       x[j] = x[j-(n-m)] ^ (y >> 1) ^ (y&1 ? a : 0);
 292     }
 293   } else if (block == 1) {
 294     // split loop to avoid costly modulo operations
 295     {  // extra scope for MSVC brokenness w.r.t. for scope
 296       for(int j = 0; j < n-m; j++) {
 297         UIntType y = (x[j+n] & upper_mask) | (x[j+n+1] & lower_mask);
 298         x[j] = x[j+n+m] ^ (y >> 1) ^ (y&1 ? a : 0);
 299       }
 300     }
 301
 302     for(int j = n-m; j < n-1; j++) {
 303       UIntType y = (x[j+n] & upper_mask) | (x[j+n+1] & lower_mask);
 304       x[j] = x[j-(n-m)] ^ (y >> 1) ^ (y&1 ? a : 0);
 305     }
 306     // last iteration
 307     UIntType y = (x[2*n-1] & upper_mask) | (x[0] & lower_mask);
 308     x[n-1] = x[m-1] ^ (y >> 1) ^ (y&1 ? a : 0);
 309     i = 0;
 310   }
 311 }
 312 /// \endcond
 313
 314 template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
 315   int s, UIntType b, int t, UIntType c, int l, UIntType val>
 316 inline typename mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::result_type
 317 mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::operator()()
 318 {
 319   if(i == n)
 320     twist(0);
 321   else if(i >= 2*n)
 322     twist(1);
 323   // Step 4
 324   UIntType z = x[i];
 325   ++i;
 326   z ^= (z >> u);
 327   z ^= ((z << s) & b);
 328   z ^= ((z << t) & c);
 329   z ^= (z >> l);
 330   return z;
 331 }
 332
 333 } // namespace random
 334
 335 /**
 336  * The specializations \mt11213b and \mt19937 are from
 337  *
 338  *  @blockquote
 339  *  "Mersenne Twister: A 623-dimensionally equidistributed
 340  *  uniform pseudo-random number generator", Makoto Matsumoto
 341  *  and Takuji Nishimura, ACM Transactions on Modeling and
 342  *  Computer Simulation: Special Issue on Uniform Random Number
 343  *  Generation, Vol. 8, No. 1, January 1998, pp. 3-30.
 344  *  @endblockquote
 345  */
 346 typedef random::mersenne_twister<uint32_t,32,351,175,19,0xccab8ee7,11,
 347   7,0x31b6ab00,15,0xffe50000,17, 0xa37d3c92> mt11213b;
 348
 349 /**
 350  * The specializations \mt11213b and \mt19937 are from
 351  *
 352  *  @blockquote
 353  *  "Mersenne Twister: A 623-dimensionally equidistributed
 354  *  uniform pseudo-random number generator", Makoto Matsumoto
 355  *  and Takuji Nishimura, ACM Transactions on Modeling and
 356  *  Computer Simulation: Special Issue on Uniform Random Number
 357  *  Generation, Vol. 8, No. 1, January 1998, pp. 3-30.
 358  *  @endblockquote
 359  */
 360 typedef random::mersenne_twister<uint32_t,32,624,397,31,0x9908b0df,11,
 361   7,0x9d2c5680,15,0xefc60000,18, 3346425566U> mt19937;
 362
 363 } // namespace boost
 364
 365 BOOST_RANDOM_PTR_HELPER_SPEC(boost::mt19937)
 366
 367 #endif // BOOST_RANDOM_MERSENNE_TWISTER_HPP