Search code examples
c++c++11randommersenne-twister

Which Mersenne Twister does C++11 provide?


I'm having trouble determining which variant of Mersenne Twister C++11 provides. Looking at Matsumoto and Nishimura ACM paper at Mersenne twister: A 623 Dimensionally Equidistributed Uniform Pseudorandom Number Generator, the authors provide the algorithm, an implementation of the algorithm, and call it MT19937.

However, when I test C++11's same-named generator with the small program below, I cannot reproduce the stream created by Matsumoto and Nishimura's MT19937. The streams differ from the very first 32-bit word produced.

Which Mersenne Twister does C++11 provide?


The program below was run on Fedora 22 using GCC, -std=c++11 and GNU's stdlibc++.

std::mt19937 prng(102013);
for (unsigned int i = 0; i <= 625; i++)
{
    cout << std::hex << prng();

    if(i+1 != 625)
        cout << ",";

    if(i && i%8 == 0)
        cout << endl;
}

Solution

  • Looking at the MT19937 from your the linked to paper and the MT19937 defined by the standard it looks like they are the same but an additional layer of tempering was added and an initialization multiplier

    If we look at the values defined by [rand.predef] 26.5.5(3) vs the parameters defined by the paper we have

    32,624,397,31,0x9908b0df,11,0xffffffff,7,0x9d2c5680,15,0xefc60000,18,1812433253 <- standard
    w ,n  ,m  ,r ,a         ,u ,d         ,s,b         ,t ,c         ,l ,f  
    32,624,397,31,0x9908b0df,11,          ,7,0x9d2c5680,15,0xefc60000,18,           <- paper
    

    This is where the difference is coming from. Also according to the standard the 10,000th iteration of std::mt19937 is 399268537