|
Rosetta
|
Mersenne Twister 19937 random number generator. More...
Classes | |
| union | W128_T |
| class | numeric::random::mt19937_RG |
Namespaces | |
| numeric | |
| Unit headers. | |
| numeric::random | |
Macros | |
| #define | inline |
| #define | PRIu64 "llu" |
| #define | PRIx64 "llx" |
| #define | UINT64_C(v) (v ## ULL) |
| #define | DSFMT_MEXP 19937 |
| #define | DSFMT_N (DSFMT_MEXP / 104) |
| #define | DSFMT_N32 (DSFMT_N * 4) |
| #define | DSFMT_N64 (DSFMT_N * 2) |
| #define | DSFMT_LOW_MASK UINT64_C(0x000FFFFFFFFFFFFF) |
| #define | DSFMT_LOW_MASK32_1 0x000fffffU |
| #define | DSFMT_LOW_MASK32_2 0xffffffffU |
| #define | DSFMT_HIGH_CONST UINT64_C(0x3FF0000000000000) |
| #define | DSFMT_HIGH_CONST32 0x3ff00000U |
| #define | DSFMT_POS1 36 |
| #define | DSFMT_SL1 29 |
| #define | DSFMT_SL2 1 |
| #define | DSFMT_SR1 7 |
| #define | DSFMT_SR2 16 |
| #define | DSFMT_MSK1 UINT64_C(0x57fbfffdffff575f) |
| #define | DSFMT_MSK2 UINT64_C(0xffff6febffffffee) |
| #define | DSFMT_MSK32_1 0x57fbfffdU |
| #define | DSFMT_MSK32_2 0xffff575fU |
| #define | DSFMT_MSK32_3 0xffff6febU |
| #define | DSFMT_MSK32_4 0xffffffeeU |
| #define | DSFMT_PCV1 UINT64_C(0x0000000000000001) |
| #define | DSFMT_PCV2 UINT64_C(0x000ec8f3d0b00000) |
| #define | DSFMT_IDSTR "dDSFMT-19937:36-29-1-7-16:57fbfffdffff575f-ffff6febffffffee" |
Typedefs | |
| typedef union W128_T | w128_t |
Functions | |
| static void | numeric::random::lshift128 (w128_t *out, const w128_t *in, int shift) |
| static uint32_t | numeric::random::ini_func1 (uint32_t x) |
| static uint32_t | numeric::random::ini_func2 (uint32_t x) |
| static int | numeric::random::sformat_idxof (int i) |
| static void | numeric::random::do_recursion (w128_t *r, w128_t *a, w128_t *b, w128_t *c, w128_t *lung) |
Mersenne Twister 19937 random number generator.
Implementation of the Mersenne Twister random number generator with "19937" parameters. Copied and pasted into wrapper class from the inventor's C code available from:
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html
It's BSD licensed so we can incorporate and redistribute it freely. I choose the "dSFMT" code, which is oriented toward generating doubles instead of ints and is highly optimized for modern processors, although I omitted the specializations for SSE2 and Altivec that are present in the original for ease of compilation. (On my machine it's still 7% faster than ran3, although random number generation is NOT the slow step in Rosetta!) This is dSFMT version 1.2.1, the most current as of Nov 2007.
The Mersenne Twister is a fairly high quality, fairly fast, and widely used pseudo-random number generator. It has many parameter sets, which differ in the amount of storage they require for their state, but 19937 is the most used.
The major advantage over ran3 is that mt19937 can be seeded from any 32-bit value, so up to ~4 billion unique simulation trajectories are possible. (In fact, it can be seeded from an array of values instead, leading to even more possibilities.) Although I can't find documentation, I understand from David Baker that ran3 can only accept seeds in the range from approx. -1 million to -4 million, meaning that only ~3 million unique simulations are possible. This sometimes causes problems for jobs running on BOINC, where jobs are distributed over many, many processors. Also, ran3 has a period length of (2**55)-1, whereas mt19937 has a period of (2**19937)-1, although I kind of doubt we're ever really running up against that limitation.
Boost.Random has an implementation also, and says this about it:
cycle length: (2**19937) - 1 good uniform distribution in up to 623 dimensions It is recommended as the default random number generator.
The GNU Scientific Library has an implementation also, and says this about it:
The MT19937 generator of Makoto Matsumoto and Takuji Nishimura is a variant of the twisted generalized feedback shift-register algorithm, and is known as the Mersenne Twister generator. It has a Mersenne prime period of 2^19937 - 1 (about 10^6000) and is equi-distributed in 623 dimensions. It has passed the DIEHARD statistical tests. It uses 624 words of state per generator and is comparable in speed to the other generators.
See Makoto Matsumoto and Takuji Nishimura, Mersenne Twister: A 623-dimensionally equidistributed uniform pseudorandom number generator. ACM Transactions on Modeling and Computer Simulation, Vol. 8, No. 1 (Jan. 1998), Pages 3-30
| #define DSFMT_HIGH_CONST UINT64_C(0x3FF0000000000000) |
| #define DSFMT_HIGH_CONST32 0x3ff00000U |
| #define DSFMT_IDSTR "dDSFMT-19937:36-29-1-7-16:57fbfffdffff575f-ffff6febffffffee" |
| #define DSFMT_LOW_MASK UINT64_C(0x000FFFFFFFFFFFFF) |
the pick up position of the array. #define DSFMT_POS1 122 the parameter of shift left as four 32-bit registers. #define DSFMT_SL1 18 the parameter of shift left as one 128-bit register. The 128-bit integer is shifted by (SL2 * 8) bits. #define DSFMT_SL2 1 the parameter of shift right as four 32-bit registers. #define DSFMT_SR1 11 the parameter of shift right as one 128-bit register. The 128-bit integer is shifted by (SL2 * 8) bits. #define DSFMT_SR2 1 A bitmask, used in the recursion. These parameters are introduced to break symmetry of SIMD. #define DSFMT_MSK1 (uint64_t)0xdfffffefULL #define DSFMT_MSK2 (uint64_t)0xddfecb7fULL These definitions are part of a 128-bit period certification vector. #define DSFMT_PCV1 UINT64_C(0x00000001) #define DSFMT_PCV2 UINT64_C(0x00000000)
| #define DSFMT_LOW_MASK32_1 0x000fffffU |
| #define DSFMT_LOW_MASK32_2 0xffffffffU |
| #define DSFMT_MEXP 19937 |
| #define DSFMT_MSK1 UINT64_C(0x57fbfffdffff575f) |
| #define DSFMT_MSK2 UINT64_C(0xffff6febffffffee) |
| #define DSFMT_MSK32_1 0x57fbfffdU |
| #define DSFMT_MSK32_2 0xffff575fU |
| #define DSFMT_MSK32_3 0xffff6febU |
| #define DSFMT_MSK32_4 0xffffffeeU |
| #define DSFMT_N (DSFMT_MEXP / 104) |
Mersenne Exponent. The period of the sequence is a multiple of 2^DSFMT_MEXP-1. #define DSFMT_MEXP 19937 DSFMT generator has an internal state array of 128-bit integers, and N is its size.
| #define DSFMT_N32 (DSFMT_N * 4) |
N32 is the size of internal state array when regarded as an array of 32-bit integers.
| #define DSFMT_N64 (DSFMT_N * 2) |
N64 is the size of internal state array when regarded as an array of 64-bit integers.
| #define DSFMT_PCV1 UINT64_C(0x0000000000000001) |
| #define DSFMT_PCV2 UINT64_C(0x000ec8f3d0b00000) |
| #define DSFMT_POS1 36 |
| #define DSFMT_SL1 29 |
| #define DSFMT_SL2 1 |
| #define DSFMT_SR1 7 |
| #define DSFMT_SR2 16 |
| #define inline |
| #define PRIu64 "llu" |
| #define PRIx64 "llx" |
| #define UINT64_C | ( | v | ) | (v ## ULL) |
1.9.1