Rosetta  2020.46
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
Classes | Namespaces | Macros | Typedefs | Functions
mt19937.hh File Reference

Mersenne Twister 19937 random number generator. More...

#include <numeric/random/uniform.hh>
#include <utility/VirtualBase.hh>
#include <cstring>
#include <iostream>
#include <cstdio>
#include <cinttypes>

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)
 

Detailed Description

Mersenne Twister 19937 random number generator.

Author
Ian W. Davis

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

Macro Definition Documentation

#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)

Referenced by numeric::random::do_recursion(), and numeric::random::mt19937_RG::initial_mask().

#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.

Referenced by numeric::random::mt19937_RG::gen_rand_all(), numeric::random::mt19937_RG::getRandom(), numeric::random::mt19937_RG::init_by_array(), numeric::random::mt19937_RG::initial_mask(), numeric::random::mt19937_RG::period_certification(), and numeric::random::mt19937_RG::setSeed().

#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.

Referenced by numeric::random::mt19937_RG::init_by_array(), and numeric::random::mt19937_RG::setSeed().

#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)

Typedef Documentation

128-bit data type