[1022] | 1 | // -*- C++ -*- |
---|
| 2 | |
---|
| 3 | /* |
---|
| 4 | * $Id$ |
---|
| 5 | * |
---|
| 6 | * A C-program for MT19937: Integer version (1998/4/6) |
---|
| 7 | * genrand() generates one pseudorandom unsigned integer (32bit) |
---|
| 8 | * which is uniformly distributed among 0 to 2^32-1 for each |
---|
| 9 | * call. sgenrand(seed) set initial values to the working area |
---|
| 10 | * of 624 words. Before genrand(), sgenrand(seed) must be |
---|
| 11 | * called once. (seed is any 32-bit integer except for 0). |
---|
| 12 | * Coded by Takuji Nishimura, considering the suggestions by |
---|
| 13 | * Topher Cooper and Marc Rieffel in July-Aug. 1997. |
---|
| 14 | * |
---|
| 15 | * This library is free software; you can redistribute it and/or |
---|
| 16 | * modify it under the terms of the GNU Library General Public |
---|
| 17 | * License as published by the Free Software Foundation; either |
---|
| 18 | * version 2 of the License, or (at your option) any later |
---|
| 19 | * version. |
---|
| 20 | * This library is distributed in the hope that it will be useful, |
---|
| 21 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
---|
| 22 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. |
---|
| 23 | * See the GNU Library General Public License for more details. |
---|
| 24 | * You should have received a copy of the GNU Library General |
---|
| 25 | * Public License along with this library; if not, write to the |
---|
| 26 | * Free Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA |
---|
| 27 | * 02111-1307 USA |
---|
| 28 | * |
---|
| 29 | * Copyright (C) 1997 Makoto Matsumoto and Takuji Nishimura. |
---|
| 30 | * When you use this, send an email to: matumoto@math.keio.ac.jp |
---|
| 31 | * with an appropriate reference to your work. |
---|
| 32 | * |
---|
| 33 | * REFERENCE |
---|
| 34 | * M. Matsumoto and T. Nishimura, |
---|
| 35 | * "Mersenne Twister: A 623-Dimensionally Equidistributed Uniform |
---|
| 36 | * Pseudo-Random Number Generator", |
---|
| 37 | * ACM Transactions on Modeling and Computer Simulation, |
---|
| 38 | * Vol. 8, No. 1, January 1998, pp 3--30. |
---|
| 39 | * |
---|
| 40 | * See |
---|
| 41 | * http://www.math.keio.ac.jp/~matumoto/emt.html |
---|
| 42 | * and |
---|
| 43 | * http://www.acm.org/pubs/citations/journals/tomacs/1998-8-1/p3-matsumoto/ |
---|
| 44 | * |
---|
| 45 | */ |
---|
| 46 | |
---|
| 47 | #ifndef BZ_RAND_MT |
---|
| 48 | #define BZ_RAND_MT |
---|
| 49 | |
---|
| 50 | #include <blitz/blitz.h> |
---|
| 51 | |
---|
| 52 | #include <vector> |
---|
| 53 | #include <string> |
---|
| 54 | #include <sstream> |
---|
| 55 | #include <iostream> |
---|
| 56 | #include <iterator> |
---|
| 57 | |
---|
| 58 | #ifndef UINT_MAX |
---|
| 59 | #include <limits.h> |
---|
| 60 | #endif |
---|
| 61 | |
---|
| 62 | #ifdef BZ_HAVE_BOOST_SERIALIZATION |
---|
| 63 | #include <boost/serialization/serialization.hpp> |
---|
| 64 | #include <boost/serialization/vector.hpp> |
---|
| 65 | #endif |
---|
| 66 | |
---|
| 67 | BZ_NAMESPACE(ranlib) |
---|
| 68 | |
---|
| 69 | #if UINT_MAX < 4294967295U |
---|
| 70 | typedef unsigned long twist_int; // must be at least 32 bits |
---|
| 71 | #else |
---|
| 72 | typedef unsigned int twist_int; |
---|
| 73 | #endif |
---|
| 74 | |
---|
| 75 | class MersenneTwister |
---|
| 76 | { |
---|
| 77 | public: |
---|
| 78 | |
---|
| 79 | private: |
---|
| 80 | |
---|
| 81 | #if defined(BZ_HAVE_NAMESPACES) && defined(BZ_HAVE_STD) |
---|
| 82 | typedef std::vector<twist_int> State; |
---|
| 83 | #else |
---|
| 84 | typedef vector<twist_int> State; |
---|
| 85 | #endif |
---|
| 86 | typedef State::size_type SizeType; |
---|
| 87 | typedef State::iterator Iter; |
---|
| 88 | |
---|
| 89 | // Implements Step 2 and half of Step 3 in the MN98 description |
---|
| 90 | struct BitMixer { |
---|
| 91 | BitMixer() : s0(0), K(0x9908b0df) {}; |
---|
| 92 | BitMixer(twist_int k) : s0(0), K(k) {}; |
---|
| 93 | |
---|
| 94 | // Return 0 if lsb of s1=0, a if lsb of s1=1. |
---|
| 95 | inline twist_int low_mask (twist_int s1) const { |
---|
| 96 | // This does not actually result in a branch because it's |
---|
| 97 | // equivalent to ( -(s1 & 1u) ) & K |
---|
| 98 | return (s1&1u) ? K : 0u; |
---|
| 99 | } |
---|
| 100 | |
---|
| 101 | // Return y>>1 in MN98 (step 2 + part of 3). |
---|
| 102 | // y = (x[i] AND u) OR (x[i+1 mod n] AND ll), where s0=x[i] and |
---|
| 103 | // s1=x[i+1 mod n] |
---|
| 104 | inline twist_int high_mask (twist_int s1) const { |
---|
| 105 | return ( (s0&0x80000000) | (s1&0x7fffffff) ) >>1; |
---|
| 106 | } |
---|
| 107 | |
---|
| 108 | // Calculate (half of) step 3 in MN98. |
---|
| 109 | inline twist_int operator() (twist_int s1) { |
---|
| 110 | // (y>>1) XOR (0 if lsb of s1=0, a if lsb of s1=1) |
---|
| 111 | // x[i+m] is XORed in reload |
---|
| 112 | // (Note that it is OK to call low_mask with s1 (x[i+1]) and not |
---|
| 113 | // with y, like MN98 does, because s1&1 == y&1 by construction. |
---|
| 114 | twist_int r = high_mask(s1) ^ low_mask(s1); |
---|
| 115 | s0 = s1; |
---|
| 116 | return r; |
---|
| 117 | } |
---|
| 118 | twist_int s0; // this is "x[i]" in the MN98 description |
---|
| 119 | const twist_int K; // MN98 "a" vector |
---|
| 120 | }; |
---|
| 121 | |
---|
| 122 | enum { N = 624, |
---|
| 123 | PF = 397, // MN98 "m" |
---|
| 124 | reference_seed = 4357 }; |
---|
| 125 | |
---|
| 126 | void initialize() |
---|
| 127 | { |
---|
| 128 | S.resize(N); |
---|
| 129 | I = S.end(); |
---|
| 130 | } |
---|
| 131 | |
---|
| 132 | public: |
---|
| 133 | MersenneTwister() : b_(0x9D2C5680), c_(0xEFC60000) |
---|
| 134 | { |
---|
| 135 | initialize(); |
---|
| 136 | seed(); |
---|
| 137 | |
---|
| 138 | // There is a problem: static initialization + templates do not |
---|
| 139 | // mix very well in C++. If you have a static member |
---|
| 140 | // of a class template, there is no guarantee on its order iin |
---|
| 141 | // static initialization. This MersenneTwister class is used |
---|
| 142 | // elsewhere as a static member of a template class, and it is |
---|
| 143 | // possible (in fact, I've done so) to create a static initializer |
---|
| 144 | // that will invoke the seed() method of this object before its |
---|
| 145 | // ctor has been called (result: crash). |
---|
| 146 | // ANSI C++ is stranger than fiction. |
---|
| 147 | // Currently the documentation forbids using RNGs from |
---|
| 148 | // static initializers. There doesn't seem to be a good |
---|
| 149 | // fix. |
---|
| 150 | } |
---|
| 151 | |
---|
| 152 | MersenneTwister(twist_int aa, twist_int bb, twist_int cc) : |
---|
| 153 | twist_(aa), b_(bb), c_(cc) |
---|
| 154 | { |
---|
| 155 | initialize(); |
---|
| 156 | seed(); |
---|
| 157 | } |
---|
| 158 | |
---|
| 159 | MersenneTwister(twist_int initial_seed) : b_(0x9D2C5680), c_(0xEFC60000) |
---|
| 160 | { |
---|
| 161 | initialize(); |
---|
| 162 | seed(initial_seed); |
---|
| 163 | } |
---|
| 164 | |
---|
| 165 | MersenneTwister(twist_int aa, twist_int bb, twist_int cc, |
---|
| 166 | twist_int initial_seed) : twist_(aa), b_(bb), c_(cc) |
---|
| 167 | { |
---|
| 168 | initialize(); |
---|
| 169 | seed(initial_seed); |
---|
| 170 | } |
---|
| 171 | |
---|
| 172 | // Seed. Uses updated seed algorithm from mt19937ar. The old |
---|
| 173 | // algorithm would yield sequences that were close from seeds that |
---|
| 174 | // were close. |
---|
| 175 | void seed (twist_int seed = reference_seed) |
---|
| 176 | { |
---|
| 177 | // seed cannot equal 0 |
---|
| 178 | if (seed == 0) |
---|
| 179 | seed = reference_seed; |
---|
| 180 | |
---|
| 181 | S[0] = seed & 0xFFFFFFFF; |
---|
| 182 | for (SizeType mti=1; mti<S.size(); ++mti) { |
---|
| 183 | S[mti] = (1812433253U * (S[mti-1] ^ (S[mti-1] >> 30)) + mti); |
---|
| 184 | S[mti] &= 0xffffffffU; |
---|
| 185 | } |
---|
| 186 | |
---|
| 187 | reload(); |
---|
| 188 | } |
---|
| 189 | |
---|
| 190 | // Seed by array, swiped directly from mt19937ar. Gives a larger |
---|
| 191 | // initial seed space. |
---|
| 192 | void seed (State seed_vector) |
---|
| 193 | { |
---|
| 194 | SizeType i, j, k; |
---|
| 195 | seed(19650218U); |
---|
| 196 | i=1; j=0; |
---|
| 197 | const SizeType N=S.size(); |
---|
| 198 | const SizeType n=seed_vector.size(); |
---|
| 199 | k = (N>n ? N : n); |
---|
| 200 | for (; k; k--) { |
---|
| 201 | S[i] = (S[i] ^ ((S[i-1] ^ (S[i-1] >> 30)) * 1664525U)) |
---|
| 202 | + seed_vector[j] + j; /* non linear */ |
---|
| 203 | S[i] &= 0xffffffffU; /* for WORDSIZE > 32 machines */ |
---|
| 204 | i++; j++; |
---|
| 205 | if (i>=N) { S[0] = S[N-1]; i=1; } |
---|
| 206 | if (j>=n) j=0; |
---|
| 207 | } |
---|
| 208 | for (k=N-1; k; k--) { |
---|
| 209 | S[i] = (S[i] ^ ((S[i-1] ^ (S[i-1] >> 30)) * 1566083941UL)) |
---|
| 210 | - i; /* non linear */ |
---|
| 211 | S[i] &= 0xffffffffU; /* for WORDSIZE > 32 machines */ |
---|
| 212 | i++; |
---|
| 213 | if (i>=N) { S[0] = S[N-1]; i=1; } |
---|
| 214 | } |
---|
| 215 | |
---|
| 216 | S[0] = 0x80000000U; /* MSB is 1; assuring non-zero initial array */ |
---|
| 217 | |
---|
| 218 | reload(); |
---|
| 219 | } |
---|
| 220 | |
---|
| 221 | // generate a full new x array |
---|
| 222 | void reload (void) |
---|
| 223 | { |
---|
| 224 | // This check is required because it is possible to call random() |
---|
| 225 | // before the constructor. See the note above about static |
---|
| 226 | // initialization. |
---|
| 227 | |
---|
| 228 | Iter p0 = S.begin(); |
---|
| 229 | Iter pM = p0 + PF; |
---|
| 230 | twist_ (S[0]); // set x[i]=x[0] in the twister (prime the pump) |
---|
| 231 | for (Iter pf_end = S.begin()+(N-PF); p0 != pf_end; ++p0, ++pM) |
---|
| 232 | // mt[kk] = mt[kk+m] XOR ((y>>1)XOR(mag01), as calc by BitMixer) |
---|
| 233 | *p0 = *pM ^ twist_ (p0[1]); |
---|
| 234 | |
---|
| 235 | // This is the "modulo part" where kk+m rolls over |
---|
| 236 | pM = S.begin(); |
---|
| 237 | for (Iter s_end = S.begin()+(N-1); p0 != s_end; ++p0, ++pM) |
---|
| 238 | *p0 = *pM ^ twist_ (p0[1]); |
---|
| 239 | // and final element where kk+1 rolls over |
---|
| 240 | *p0 = *pM ^ twist_ (S[0]); |
---|
| 241 | |
---|
| 242 | I = S.begin(); |
---|
| 243 | } |
---|
| 244 | |
---|
| 245 | inline twist_int random (void) |
---|
| 246 | { |
---|
| 247 | if (I >= S.end()) reload(); |
---|
| 248 | // get next word from array |
---|
| 249 | twist_int y = *I++; |
---|
| 250 | // Step 4+5 in MN98, multiply by tempering matrix |
---|
| 251 | y ^= (y >> 11); |
---|
| 252 | y ^= (y << 7) & b_; |
---|
| 253 | y ^= (y << 15) & c_; |
---|
| 254 | y ^= (y >> 18); |
---|
| 255 | return y; |
---|
| 256 | } |
---|
| 257 | |
---|
| 258 | // functions for getting/setting state |
---|
| 259 | class mt_state { |
---|
| 260 | friend class MersenneTwister; |
---|
| 261 | private: |
---|
| 262 | State S; |
---|
| 263 | State::difference_type I; |
---|
| 264 | public: |
---|
| 265 | mt_state() { } |
---|
| 266 | mt_state(State s, State::difference_type i) : S(s), I(i) { } |
---|
| 267 | mt_state(const std::string& s) { |
---|
| 268 | std::istringstream is(s); |
---|
| 269 | is >> I; |
---|
| 270 | S = State(std::istream_iterator<twist_int>(is), |
---|
| 271 | std::istream_iterator<twist_int>()); |
---|
| 272 | assert(!S.empty()); |
---|
| 273 | } |
---|
| 274 | operator bool() const { return !S.empty(); } |
---|
| 275 | std::string str() const { |
---|
| 276 | if (S.empty()) |
---|
| 277 | return std::string(); |
---|
| 278 | std::ostringstream os; |
---|
| 279 | os << I << " "; |
---|
| 280 | std::copy(S.begin(), S.end(), |
---|
| 281 | std::ostream_iterator<twist_int>(os," ")); |
---|
| 282 | return os.str(); |
---|
| 283 | } |
---|
| 284 | #ifdef BZ_HAVE_BOOST_SERIALIZATION |
---|
| 285 | friend class boost::serialization::access; |
---|
| 286 | /** Serialization operator. Relies on the ability to serialize |
---|
| 287 | std::vector. */ |
---|
| 288 | template<class T_arch> |
---|
| 289 | void serialize(T_arch& ar, const unsigned int version) { |
---|
| 290 | ar & S & I; |
---|
| 291 | }; |
---|
| 292 | #endif |
---|
| 293 | |
---|
| 294 | }; |
---|
| 295 | |
---|
| 296 | typedef mt_state T_state; |
---|
| 297 | T_state getState() const { return T_state(S, I-S.begin()); } |
---|
| 298 | std::string getStateString() const { |
---|
| 299 | T_state tmp(S, I-S.begin()); |
---|
| 300 | return tmp.str(); |
---|
| 301 | } |
---|
| 302 | void setState(const T_state& s) { |
---|
| 303 | if (!s) { |
---|
| 304 | std::cerr << "Error: state is empty" << std::endl; |
---|
| 305 | return; |
---|
| 306 | } |
---|
| 307 | S = s.S; |
---|
| 308 | I = S.begin() + s.I; |
---|
| 309 | } |
---|
| 310 | void setState(const std::string& s) { |
---|
| 311 | T_state tmp(s); |
---|
| 312 | setState(tmp); |
---|
| 313 | } |
---|
| 314 | |
---|
| 315 | private: |
---|
| 316 | BitMixer twist_; |
---|
| 317 | const twist_int b_,c_; |
---|
| 318 | |
---|
| 319 | State S; |
---|
| 320 | Iter I; |
---|
| 321 | }; |
---|
| 322 | |
---|
| 323 | |
---|
| 324 | /** This class creates MersenneTwisters with different parameters |
---|
| 325 | indexed by and ID number. */ |
---|
| 326 | class MersenneTwisterCreator |
---|
| 327 | { |
---|
| 328 | public: |
---|
| 329 | static MersenneTwister create(unsigned int i) { |
---|
| 330 | // We only have n different parameter sets |
---|
| 331 | i = i % n; |
---|
| 332 | return MersenneTwister(a_[i], b_[i], c_[i]); |
---|
| 333 | }; |
---|
| 334 | |
---|
| 335 | private: |
---|
| 336 | static const unsigned int n=48; |
---|
| 337 | static const twist_int a_[n]; |
---|
| 338 | static const twist_int b_[n]; |
---|
| 339 | static const twist_int c_[n]; |
---|
| 340 | }; |
---|
| 341 | |
---|
| 342 | BZ_NAMESPACE_END |
---|
| 343 | |
---|
| 344 | #endif // BZ_RAND_MT |
---|