stc/exp/ml_stc_linux_make_v1.0/include/boost/random/mersenne_twister.hpp

   1 /* boost random/mersenne_twister.hpp header file\r
   2  *\r
   3  * Copyright Jens Maurer 2000-2001\r
   4  * Distributed under the Boost Software License, Version 1.0. (See\r
   5  * accompanying file LICENSE_1_0.txt or copy at\r
   6  * http://www.boost.org/LICENSE_1_0.txt)\r
   7  *\r
   8  * See http://www.boost.org for most recent version including documentation.\r
   9  *\r
  10  * $Id: mersenne_twister.hpp 53871 2009-06-13 17:54:06Z steven_watanabe $\r
  11  *\r
  12  * Revision history\r
  13  *  2001-02-18  moved to individual header files\r
  14  */\r
  15 \r
  16 #ifndef BOOST_RANDOM_MERSENNE_TWISTER_HPP\r
  17 #define BOOST_RANDOM_MERSENNE_TWISTER_HPP\r
  18 \r
  19 #include <iostream>\r
  20 #include <algorithm>     // std::copy\r
  21 #include <stdexcept>\r
  22 #include <boost/config.hpp>\r
  23 #include <boost/limits.hpp>\r
  24 #include <boost/static_assert.hpp>\r
  25 #include <boost/integer_traits.hpp>\r
  26 #include <boost/cstdint.hpp>\r
  27 #include <boost/random/linear_congruential.hpp>\r
  28 #include <boost/detail/workaround.hpp>\r
  29 #include <boost/random/detail/config.hpp>\r
  30 #include <boost/random/detail/ptr_helper.hpp>\r
  31 #include <boost/random/detail/seed.hpp>\r
  32 \r
  33 namespace boost {\r
  34 namespace random {\r
  35 \r
  36 // http://www.math.keio.ac.jp/matumoto/emt.html\r
  37 template<class UIntType, int w, int n, int m, int r, UIntType a, int u,\r
  38   int s, UIntType b, int t, UIntType c, int l, UIntType val>\r
  39 class mersenne_twister\r
  40 {\r
  41 public:\r
  42   typedef UIntType result_type;\r
  43   BOOST_STATIC_CONSTANT(int, word_size = w);\r
  44   BOOST_STATIC_CONSTANT(int, state_size = n);\r
  45   BOOST_STATIC_CONSTANT(int, shift_size = m);\r
  46   BOOST_STATIC_CONSTANT(int, mask_bits = r);\r
  47   BOOST_STATIC_CONSTANT(UIntType, parameter_a = a);\r
  48   BOOST_STATIC_CONSTANT(int, output_u = u);\r
  49   BOOST_STATIC_CONSTANT(int, output_s = s);\r
  50   BOOST_STATIC_CONSTANT(UIntType, output_b = b);\r
  51   BOOST_STATIC_CONSTANT(int, output_t = t);\r
  52   BOOST_STATIC_CONSTANT(UIntType, output_c = c);\r
  53   BOOST_STATIC_CONSTANT(int, output_l = l);\r
  54 \r
  55   BOOST_STATIC_CONSTANT(bool, has_fixed_range = false);\r
  56   \r
  57   mersenne_twister() { seed(); }\r
  58 \r
  59   BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(mersenne_twister, UIntType, value)\r
  60   { seed(value); }\r
  61   template<class It> mersenne_twister(It& first, It last) { seed(first,last); }\r
  62 \r
  63   BOOST_RANDOM_DETAIL_GENERATOR_CONSTRUCTOR(mersenne_twister, Generator, gen)\r
  64   { seed(gen); }\r
  65 \r
  66   // compiler-generated copy ctor and assignment operator are fine\r
  67 \r
  68   void seed() { seed(UIntType(5489)); }\r
  69 \r
  70   BOOST_RANDOM_DETAIL_ARITHMETIC_SEED(mersenne_twister, UIntType, value)\r
  71   {\r
  72     // New seeding algorithm from \r
  73     // http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/emt19937ar.html\r
  74     // In the previous versions, MSBs of the seed affected only MSBs of the\r
  75     // state x[].\r
  76     const UIntType mask = ~0u;\r
  77     x[0] = value & mask;\r
  78     for (i = 1; i < n; i++) {\r
  79       // See Knuth "The Art of Computer Programming" Vol. 2, 3rd ed., page 106\r
  80       x[i] = (1812433253UL * (x[i-1] ^ (x[i-1] >> (w-2))) + i) & mask;\r
  81     }\r
  82   }\r
  83 \r
  84   // For GCC, moving this function out-of-line prevents inlining, which may\r
  85   // reduce overall object code size.  However, MSVC does not grok\r
  86   // out-of-line definitions of member function templates.\r
  87   BOOST_RANDOM_DETAIL_GENERATOR_SEED(mersenne_twister, Generator, gen)\r
  88   {\r
  89 #ifndef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS\r
  90     BOOST_STATIC_ASSERT(!std::numeric_limits<result_type>::is_signed);\r
  91 #endif\r
  92     // I could have used std::generate_n, but it takes "gen" by value\r
  93     for(int j = 0; j < n; j++)\r
  94       x[j] = gen();\r
  95     i = n;\r
  96   }\r
  97 \r
  98   template<class It>\r
  99   void seed(It& first, It last)\r
 100   {\r
 101     int j;\r
 102     for(j = 0; j < n && first != last; ++j, ++first)\r
 103       x[j] = *first;\r
 104     i = n;\r
 105     if(first == last && j < n)\r
 106       throw std::invalid_argument("mersenne_twister::seed");\r
 107   }\r
 108   \r
 109   result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return 0; }\r
 110   result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const\r
 111   {\r
 112     // avoid "left shift count >= with of type" warning\r
 113     result_type res = 0;\r
 114     for(int j = 0; j < w; ++j)\r
 115       res |= (1u << j);\r
 116     return res;\r
 117   }\r
 118 \r
 119   result_type operator()();\r
 120   static bool validation(result_type v) { return val == v; }\r
 121 \r
 122 #ifndef BOOST_NO_OPERATORS_IN_NAMESPACE\r
 123 \r
 124 #ifndef BOOST_RANDOM_NO_STREAM_OPERATORS\r
 125   template<class CharT, class Traits>\r
 126   friend std::basic_ostream<CharT,Traits>&\r
 127   operator<<(std::basic_ostream<CharT,Traits>& os, const mersenne_twister& mt)\r
 128   {\r
 129     for(int j = 0; j < mt.state_size; ++j)\r
 130       os << mt.compute(j) << " ";\r
 131     return os;\r
 132   }\r
 133 \r
 134   template<class CharT, class Traits>\r
 135   friend std::basic_istream<CharT,Traits>&\r
 136   operator>>(std::basic_istream<CharT,Traits>& is, mersenne_twister& mt)\r
 137   {\r
 138     for(int j = 0; j < mt.state_size; ++j)\r
 139       is >> mt.x[j] >> std::ws;\r
 140     // MSVC (up to 7.1) and Borland (up to 5.64) don't handle the template\r
 141     // value parameter "n" available from the class template scope, so use\r
 142     // the static constant with the same value\r
 143     mt.i = mt.state_size;\r
 144     return is;\r
 145   }\r
 146 #endif\r
 147 \r
 148   friend bool operator==(const mersenne_twister& x, const mersenne_twister& y)\r
 149   {\r
 150     for(int j = 0; j < state_size; ++j)\r
 151       if(x.compute(j) != y.compute(j))\r
 152         return false;\r
 153     return true;\r
 154   }\r
 155 \r
 156   friend bool operator!=(const mersenne_twister& x, const mersenne_twister& y)\r
 157   { return !(x == y); }\r
 158 #else\r
 159   // Use a member function; Streamable concept not supported.\r
 160   bool operator==(const mersenne_twister& rhs) const\r
 161   {\r
 162     for(int j = 0; j < state_size; ++j)\r
 163       if(compute(j) != rhs.compute(j))\r
 164         return false;\r
 165     return true;\r
 166   }\r
 167 \r
 168   bool operator!=(const mersenne_twister& rhs) const\r
 169   { return !(*this == rhs); }\r
 170 #endif\r
 171 \r
 172 private:\r
 173   // returns x(i-n+index), where index is in 0..n-1\r
 174   UIntType compute(unsigned int index) const\r
 175   {\r
 176     // equivalent to (i-n+index) % 2n, but doesn't produce negative numbers\r
 177     return x[ (i + n + index) % (2*n) ];\r
 178   }\r
 179   void twist(int block);\r
 180 \r
 181   // state representation: next output is o(x(i))\r
 182   //   x[0]  ... x[k] x[k+1] ... x[n-1]     x[n]     ... x[2*n-1]   represents\r
 183   //  x(i-k) ... x(i) x(i+1) ... x(i-k+n-1) x(i-k-n) ... x[i(i-k-1)]\r
 184   // The goal is to always have x(i-n) ... x(i-1) available for\r
 185   // operator== and save/restore.\r
 186 \r
 187   UIntType x[2*n]; \r
 188   int i;\r
 189 };\r
 190 \r
 191 #ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION\r
 192 //  A definition is required even for integral static constants\r
 193 template<class UIntType, int w, int n, int m, int r, UIntType a, int u,\r
 194   int s, UIntType b, int t, UIntType c, int l, UIntType val>\r
 195 const bool mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::has_fixed_range;\r
 196 template<class UIntType, int w, int n, int m, int r, UIntType a, int u,\r
 197   int s, UIntType b, int t, UIntType c, int l, UIntType val>\r
 198 const int mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::state_size;\r
 199 template<class UIntType, int w, int n, int m, int r, UIntType a, int u,\r
 200   int s, UIntType b, int t, UIntType c, int l, UIntType val>\r
 201 const int mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::shift_size;\r
 202 template<class UIntType, int w, int n, int m, int r, UIntType a, int u,\r
 203   int s, UIntType b, int t, UIntType c, int l, UIntType val>\r
 204 const int mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::mask_bits;\r
 205 template<class UIntType, int w, int n, int m, int r, UIntType a, int u,\r
 206   int s, UIntType b, int t, UIntType c, int l, UIntType val>\r
 207 const UIntType mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::parameter_a;\r
 208 template<class UIntType, int w, int n, int m, int r, UIntType a, int u,\r
 209   int s, UIntType b, int t, UIntType c, int l, UIntType val>\r
 210 const int mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::output_u;\r
 211 template<class UIntType, int w, int n, int m, int r, UIntType a, int u,\r
 212   int s, UIntType b, int t, UIntType c, int l, UIntType val>\r
 213 const int mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::output_s;\r
 214 template<class UIntType, int w, int n, int m, int r, UIntType a, int u,\r
 215   int s, UIntType b, int t, UIntType c, int l, UIntType val>\r
 216 const UIntType mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::output_b;\r
 217 template<class UIntType, int w, int n, int m, int r, UIntType a, int u,\r
 218   int s, UIntType b, int t, UIntType c, int l, UIntType val>\r
 219 const int mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::output_t;\r
 220 template<class UIntType, int w, int n, int m, int r, UIntType a, int u,\r
 221   int s, UIntType b, int t, UIntType c, int l, UIntType val>\r
 222 const UIntType mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::output_c;\r
 223 template<class UIntType, int w, int n, int m, int r, UIntType a, int u,\r
 224   int s, UIntType b, int t, UIntType c, int l, UIntType val>\r
 225 const int mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::output_l;\r
 226 #endif\r
 227 \r
 228 template<class UIntType, int w, int n, int m, int r, UIntType a, int u,\r
 229   int s, UIntType b, int t, UIntType c, int l, UIntType val>\r
 230 void mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::twist(int block)\r
 231 {\r
 232   const UIntType upper_mask = (~0u) << r;\r
 233   const UIntType lower_mask = ~upper_mask;\r
 234 \r
 235   if(block == 0) {\r
 236     for(int j = n; j < 2*n; j++) {\r
 237       UIntType y = (x[j-n] & upper_mask) | (x[j-(n-1)] & lower_mask);\r
 238       x[j] = x[j-(n-m)] ^ (y >> 1) ^ (y&1 ? a : 0);\r
 239     }\r
 240   } else if (block == 1) {\r
 241     // split loop to avoid costly modulo operations\r
 242     {  // extra scope for MSVC brokenness w.r.t. for scope\r
 243       for(int j = 0; j < n-m; j++) {\r
 244         UIntType y = (x[j+n] & upper_mask) | (x[j+n+1] & lower_mask);\r
 245         x[j] = x[j+n+m] ^ (y >> 1) ^ (y&1 ? a : 0);\r
 246       }\r
 247     }\r
 248     \r
 249     for(int j = n-m; j < n-1; j++) {\r
 250       UIntType y = (x[j+n] & upper_mask) | (x[j+n+1] & lower_mask);\r
 251       x[j] = x[j-(n-m)] ^ (y >> 1) ^ (y&1 ? a : 0);\r
 252     }\r
 253     // last iteration\r
 254     UIntType y = (x[2*n-1] & upper_mask) | (x[0] & lower_mask);\r
 255     x[n-1] = x[m-1] ^ (y >> 1) ^ (y&1 ? a : 0);\r
 256     i = 0;\r
 257   }\r
 258 }\r
 259 \r
 260 template<class UIntType, int w, int n, int m, int r, UIntType a, int u,\r
 261   int s, UIntType b, int t, UIntType c, int l, UIntType val>\r
 262 inline typename mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::result_type\r
 263 mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::operator()()\r
 264 {\r
 265   if(i == n)\r
 266     twist(0);\r
 267   else if(i >= 2*n)\r
 268     twist(1);\r
 269   // Step 4\r
 270   UIntType z = x[i];\r
 271   ++i;\r
 272   z ^= (z >> u);\r
 273   z ^= ((z << s) & b);\r
 274   z ^= ((z << t) & c);\r
 275   z ^= (z >> l);\r
 276   return z;\r
 277 }\r
 278 \r
 279 } // namespace random\r
 280 \r
 281 \r
 282 typedef random::mersenne_twister<uint32_t,32,351,175,19,0xccab8ee7,11,\r
 283   7,0x31b6ab00,15,0xffe50000,17, 0xa37d3c92> mt11213b;\r
 284 \r
 285 // validation by experiment from mt19937.c\r
 286 typedef random::mersenne_twister<uint32_t,32,624,397,31,0x9908b0df,11,\r
 287   7,0x9d2c5680,15,0xefc60000,18, 3346425566U> mt19937;\r
 288 \r
 289 } // namespace boost\r
 290 \r
 291 BOOST_RANDOM_PTR_HELPER_SPEC(boost::mt19937)\r
 292 \r
 293 #endif // BOOST_RANDOM_MERSENNE_TWISTER_HPP\r