34
$\begingroup$

The Mersenne Twister is widely regarded as good. Heck, the CPython source says that it "is one of the most extensively tested generators in existence." But what does this mean? When asked to list properties of this generator, most of what I can offer is bad:

  • It's massive and inflexible (eg. no seeking or multiple streams),
  • It fails standard statistical tests despite its massive state size,
  • It has serious problems around 0, suggesting that it randomizes itself pretty poorly,
  • It's hardly fast

and so on. Compared to simple RNGs like XorShift*, it's also hopelessly complicated.

So I looked for some information about why this was ever thought to be good. The original paper makes lots of comments on the "super astronomical" period and 623-dimensional equidistribution, saying

Among many known measures, the tests based on the higher dimensional uniformity, such as the spectral test (c.f., Knuth [1981]) and the k-distribution test, described below, are considered to be strongest.

But, for this property, the generator is beaten by a counter of sufficient length! This makes no commentary of local distributions, which is what you actually care about in a generator (although "local" can mean various things). And even CSPRNGs don't care for such large periods, since it's just not remotely important.

There's a lot of maths in the paper, but as far as I can tell little of this is actually about randomness quality. Pretty much every mention of that quickly jumps back to these original, largely useless claims.

It seems like people jumped onto this bandwagon at the expense of older, more reliable technologies. For example, if you just up the number of words in an LCG to 3 (much less than the "only 624" of a Mersenne Twister) and output the top word each pass, it passes BigCrush (the harder part of the TestU01 test suite), despite the Twister failing it (PCG paper, fig. 2). Given this, and the weak evidence I was able to find in support of the Mersenne Twister, what did cause attention to favour it over the other choices?

This isn't purely historical either. I've been told in passing that the Mersenne Twister is at least more proven in practice than, say, PCG random. But are use-cases so discerning that they can do better than our batteries of tests? Some Googling suggests they're probably not.

In short, I'm wondering how the Mersenne Twister got its widespread positive reputation, both in its historical context and otherwise. On one hand I'm obviously skeptical of its qualities, but on the other it's hard to imagine that it was an entirely randomly occurrence.

$\endgroup$
  • 2
    $\begingroup$ I think you're right. Mersenne Twister is nothing particularly special. It's just well-known (and many of the other well-known PRNGs happen to be worse). There are other PRNGs that are also quite good. For an even better PRNG, one can use a cryptographic PRNG. I'm not sure what kind of answer one can give, though, beyond "there's nothing wrong with your reasoning". $\endgroup$ – D.W. Nov 29 '15 at 0:20
  • 1
    $\begingroup$ I think the question that you should be asking isn't whether or not MT is good (since it is, by many metrics), but why it's more commonly used than the alternatives like PCG or XorShift. The answer is probably that it's just been around for longer, and was the best reasonable default for a long time (in Internet years). $\endgroup$ – Pseudonym Nov 29 '15 at 3:18
  • 1
    $\begingroup$ @vzn "another consideration is generation time; PRNGs "quality" comes at the expense of run time" → Except that the Mersenne Twister is slower and worse than a resonably large LCG. See Fig. 16 in the PCG paper. (About whether I've read the paper: I've read most of the non-maths parts of the Mersenne Twister paper in detail and all of the PCG random paper. I mostly skimmed the third, though.) $\endgroup$ – Veedrac Nov 29 '15 at 3:25
  • 1
    $\begingroup$ Are you talking about XorShift or the KISS algorithms? $\endgroup$ – gnasher729 Nov 29 '15 at 22:36
  • 1
    $\begingroup$ @gnasher729 I mention XorShift*, but I'm not really being specific to a particular alternative. I didn't know about KISS, FWIW. $\endgroup$ – Veedrac Nov 30 '15 at 6:28
12
+100
$\begingroup$

MT was regarded as good for some years, until it was found out to be pretty bad with the more advanced TestU01 BigCrush tests and better PRNGs.

The table at pcg-random.org e.g. gives a good overview of features of some of the most used PRNGs, where the only "good" feature of the Mersenne Twister is the huge period, $2^{219937}$ and the possibility to use a seed (Reproducible Results), it passes the simple and fast TestU01 SmallCrush tests, but it fails some of the newer statistical quality tests, esp. TestU01's LinearComp Test and the TestU01's Crush and BigCrush Batteries.

This page lists the Mersenne-Twister features in detail:

Positive Qualities

  • Produces 32-bit or 64-bit numbers (thus usable as source of random bits)
  • Passes most statistical tests

Neutral Qualities

  • Inordinately huge period of $2^{219937} - 1$
  • 623-dimensionally equidistributed
  • Period can be partitioned to emulate multiple streams

Negative Qualities

  • Fails some statistical tests, with as few as 45,000 numbers.
  • Predictable — after 624 outputs, we can completely predict its output.
  • Generator state occupies 2504 bytes of RAM — in contrast, an extremely usable generator with a huger-than-anyone-can-ever-use period can fit in 8 bytes of RAM.
  • Not particularly fast.
  • Not particularly space efficient. The generator uses 20000 bits to store its internal state (20032 bits on 64-bit machines), but has a period of only $2^{219937}$, a factor of 263 (or 295) fewer than an ideal generator of the same size.
  • Uneven in its output; the generator can get into “bad states” that are slow to recover from.
  • Seedings that only differ slightly take a long time to diverge from each other; seeding must be done carefully to avoid bad states.
  • While jump-ahead is possible, algorithms to do so are slow to compute (i.e., require several seconds) and rarely provided by implementations.

Summary: Mersenne Twister is not good enough anymore, but most applications and libraries are not there yet.

$\endgroup$
  • 6
    $\begingroup$ Thanks for the nice summary! However, I am concerned that the only apparent source for your post is a website that is effectively an advertisement for another family of random number generators which has not yet been peer-reviewed. The website itself does not offer any references for the entries but the proposed article seems to contain many. Hence, I think you can improve your answer for the context here (criticism of MT) by giving references for the individual points. $\endgroup$ – Raphael Feb 22 '16 at 13:34
  • 8
    $\begingroup$ Are they seriously quibbling that the period is only $2^{219937}$ rather than $295\times 2^{219937} \approx 2^{219945}$, and that after saying that a long period is a "neutral" property of a prng? $\endgroup$ – David Richerby Feb 22 '16 at 15:51
  • 1
    $\begingroup$ "Predictable" -- MT isn't intended as a cryptographic PRNG so please edit your answer. $\endgroup$ – Jason S May 29 '17 at 16:55
6
$\begingroup$

I am the Editor who accepted the MT paper in ACM TOMS back in 1998 and I am also the designer of TestU01. I do not use MT, but mostly MRG32k3a, MRG31k3p, and LRSR113. To know more about these, about MT, and about what else there is, you can look at the following papers:

F. Panneton, P. L'Ecuyer, and M. Matsumoto, ``Improved Long-Period Generators Based on Linear Recurrences Modulo 2'', ACM Transactions on Mathematical Software, 32, 1 (2006), 1-16.

P. L'Ecuyer, ``Random Number Generation'', chapter 3 of the Handbook of Computational Statistics, J. E. Gentle, W. Haerdle, and Y. Mori, eds., Second Edition, Springer-Verlag, 2012, 35-71. https://link.springer.com/chapter/10.1007/978-3-642-21551-3_3

P. L'Ecuyer, D. Munger, B. Oreshkin, and R. Simard, ``Random Numbers for Parallel Computers: Requirements and Methods,'' Mathematics and Computers in Simulation, 135, (2017), 3-17. http://www.sciencedirect.com/science/article/pii/S0378475416300829?via%3Dihub

P. L'Ecuyer, ``Random Number Generation with Multiple Streams for Sequential and Parallel Computers,'' invited advanced tutorial, Proceedings of the 2015 Winter Simulation Conference, IEEE Press, 2015, 31-44.

$\endgroup$
  • 2
    $\begingroup$ Thanks for your answer! Would you mind adding something towards the question? 1) Why did you think MT was good (or at least worth publishing) then? 2) Why do you not think it's good enough for use? $\endgroup$ – Raphael Oct 15 '17 at 4:30
  • $\begingroup$ Thanks for adding that valuable historical context. I'm also curious about Raphael's questions and your personal thoughts when you accepted the paper. $\endgroup$ – Veedrac Oct 15 '17 at 6:31
5
$\begingroup$

Somewhat like sorting algorithms in this regard, there is no "one size fits all" PRNG. Different ones are used for different purposes and there is a wide variety of design criteria and uses. It is possible to misapply PRNGs, such as using one for cryptography that it is not designed for. Wikipedia's entry on Mersenne Twister also mentions that it was not designed for "Monte-Carlo simulations that require independent random number generators".

As noted on Wikipedia, this PRNG is indeed used in a large number of programming languages and applications even as a default PRNG. It would take a near-sociological analysis to explain why one PRNG is favored. Some possible factors that may be contributing to this PRNG:

  • The Author has good/ strong scientific credentials in area and has been working in PRNGs for decades.

  • It was specifically designed to be superior to other methods at the time.

  • The author is engaged in implementations and tracking them, also contributing to them. Some PRNGs are more theoretical and the authors do not always concern themselves with actual implementations.

  • The system is well supported/updated on a web page.

  • New versions of the PRNG have been developed to deal with weaknesses. There is not one single Mersenne Twister algorithm, its more like different versions and a family of variants which can handle different needs.

  • It has been extensively analyzed/tested by standard randomness analysis software and passed, by independent authorities.

  • There is a known effect measured with for web sites and many other contexts like scientific citations called "preferential attachment" which can be measured. It's basically where long established historical sources accrue further usage. Such an effect could explain PRNG choices over time.

In other words, you are asking about a phenomenon of "popularity" which is associated and interrelated with human choices and is not strictly tied to particular qualities, but is a sort of complex/emergent property and interplay between different algorithms, users, and environment/usage contexts.

Here is one such independent analysis of the algorithm Mersenne Twister – A Pseudo Random Number Generator and its Variants by Jagannatam (15p). The concluding paragraph is essentially an answer to your question. quoting only the 1st few sentences:

Mersenne Twister is theoretically proven to be a good PRNG, with a long period and high equidistribution. It is extensively used in the fields of simulation and modulation. The defects found by the users have been corrected by the inventors. MT has been upgraded, to use and to be compatible with the newly emerging technologies of CPU’s such as SIMD and parallel pipelines in its version of SFMT.

$\endgroup$
  • 2
    $\begingroup$ Thanks. Some of what you're saying sounds quite vague, though, like "It was specifically designed to be superior to other methods at the time." and "It has been extensively analyzed/tested by standard randomness analysis software and passed, by independent authorities.", which are exactly the claims I'm suspicious about. I'll dive into the paper a bit, though, to see if that clears things up. $\endgroup$ – Veedrac Nov 30 '15 at 6:44
  • $\begingroup$ One other thing to take into account is scientific reproducibility. Many scientists who work in the Monte Carlo simulation area go to a lot of trouble to make sure that the program as a whole produces the same output given the same seed, regardless of the number of threads. Many of them require bug-for-bug compatibility with the reference implementation of the PRNG. $\endgroup$ – Pseudonym Nov 30 '15 at 6:45
  • 2
    $\begingroup$ You also say, "New versions of the PRNG have been developed to deal with weaknesses.", but given most implementations are the bog-standard first version this sounds more like a criticism to me. I'm also a little surprised to see "The system is well supported/updated on a web page." -- how much support does a LCG need really!? $\endgroup$ – Veedrac Nov 30 '15 at 6:45
  • $\begingroup$ @Pseudonym I don't really follow. Why would that preclude using a different generator? Obviously you have to use the same generator when re-running tests, but why for new tests? $\endgroup$ – Veedrac Nov 30 '15 at 6:48
  • $\begingroup$ there does not seem much vagueness about all the scientific analysis in the original and subsequent papers and the original question is somewhat "loaded" in this way (afaik many PRNGs with less analysis/ support are used). re Pseudonyms point, afaik all PRNGs are repeatable using the same starting seeds, only hardware-based generators are not (and they are not really PRNGs any more but "real physical noise/ randomness"). not sure how this is supposedly difficult to ensure with multiple threads (dont know why separate threads cant use identical algorithm with different seeds) $\endgroup$ – vzn Nov 30 '15 at 17:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.