1 /* boost random/mersenne_twister.hpp header file
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)
8 * See http://www.boost.org for most recent version including documentation.
10 * $Id: mersenne_twister.hpp 60755 2010-03-22 00:45:06Z steven_watanabe $
13 * 2001-02-18 moved to individual header files
16 #ifndef BOOST_RANDOM_MERSENNE_TWISTER_HPP
17 #define BOOST_RANDOM_MERSENNE_TWISTER_HPP
20 #include <algorithm> // std::copy
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>
37 * Instantiations of class template mersenne_twister model a
38 * \pseudo_random_number_generator. It uses the algorithm described in
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.
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.
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>.
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.
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.
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
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);
82 BOOST_STATIC_CONSTANT(bool, has_fixed_range = false);
85 * Constructs a @c mersenne_twister and calls @c seed().
87 mersenne_twister() { seed(); }
90 * Constructs a @c mersenne_twister and calls @c seed(value).
92 BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(mersenne_twister, UIntType, value)
94 template<class It> mersenne_twister(It& first, It last) { seed(first,last); }
97 * Constructs a mersenne_twister and calls @c seed(gen).
100 * The copy constructor will always be preferred over
101 * the templated constructor.
104 BOOST_RANDOM_DETAIL_GENERATOR_CONSTRUCTOR(mersenne_twister, Generator, gen)
107 // compiler-generated copy ctor and assignment operator are fine
109 /** Calls @c seed(result_type(5489)). */
110 void seed() { seed(UIntType(5489)); }
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().
117 BOOST_RANDOM_DETAIL_ARITHMETIC_SEED(mersenne_twister, UIntType, value)
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
123 const UIntType mask = ~0u;
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;
132 * Sets the state of this mersenne_twister to the values
133 * returned by n invocations of gen.
135 * Complexity: Exactly n invocations of gen.
137 BOOST_RANDOM_DETAIL_GENERATOR_SEED(mersenne_twister, Generator, gen)
139 #ifndef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS
140 BOOST_STATIC_ASSERT(!std::numeric_limits<result_type>::is_signed);
142 // I could have used std::generate_n, but it takes "gen" by value
143 for(int j = 0; j < n; j++)
149 void seed(It& first, It last)
152 for(j = 0; j < n && first != last; ++j, ++first)
155 if(first == last && j < n)
156 throw std::invalid_argument("mersenne_twister::seed");
159 result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return 0; }
160 result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const
162 // avoid "left shift count >= with of type" warning
164 for(int j = 0; j < w; ++j)
169 result_type operator()();
170 static bool validation(result_type v) { return val == v; }
172 #ifndef BOOST_NO_OPERATORS_IN_NAMESPACE
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)
179 for(int j = 0; j < mt.state_size; ++j)
180 os << mt.compute(j) << " ";
184 template<class CharT, class Traits>
185 friend std::basic_istream<CharT,Traits>&
186 operator>>(std::basic_istream<CharT,Traits>& is, mersenne_twister& mt)
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;
198 friend bool operator==(const mersenne_twister& x, const mersenne_twister& y)
200 for(int j = 0; j < state_size; ++j)
201 if(x.compute(j) != y.compute(j))
206 friend bool operator!=(const mersenne_twister& x, const mersenne_twister& y)
207 { return !(x == y); }
209 // Use a member function; Streamable concept not supported.
210 bool operator==(const mersenne_twister& rhs) const
212 for(int j = 0; j < state_size; ++j)
213 if(compute(j) != rhs.compute(j))
218 bool operator!=(const mersenne_twister& rhs) const
219 { return !(*this == rhs); }
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
227 // equivalent to (i-n+index) % 2n, but doesn't produce negative numbers
228 return x[ (i + n + index) % (2*n) ];
230 void twist(int block);
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.
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;
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)
285 const UIntType upper_mask = (~0u) << r;
286 const UIntType lower_mask = ~upper_mask;
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);
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);
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);
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);
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()()
333 } // namespace random
336 * The specializations \mt11213b and \mt19937 are from
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.
346 typedef random::mersenne_twister<uint32_t,32,351,175,19,0xccab8ee7,11,
347 7,0x31b6ab00,15,0xffe50000,17, 0xa37d3c92> mt11213b;
350 * The specializations \mt11213b and \mt19937 are from
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.
360 typedef random::mersenne_twister<uint32_t,32,624,397,31,0x9908b0df,11,
361 7,0x9d2c5680,15,0xefc60000,18, 3346425566U> mt19937;
365 BOOST_RANDOM_PTR_HELPER_SPEC(boost::mt19937)
367 #endif // BOOST_RANDOM_MERSENNE_TWISTER_HPP