Mersenne Twister 19937 random number generator. More...

#include <numeric/random/uniform.hh>
#include <utility/pointer/ReferenceCount.hh>
#include <cstring>
#include <iostream>
#include <stdio.h>
#include <inttypes.h>

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)

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

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

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

#define DSFMT_MSK2 UINT64_C(0xffff6febffffffee)

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

#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(), numeric::random::mt19937_RG::restoreState(), numeric::random::mt19937_RG::saveState(), and numeric::random::mt19937_RG::setSeed().