44
$\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$ can you cite a ref that a counter beats it on the test? (its not clear which test you are referring to. the quoted section mentions 3)... long periods are a long accepted aspect of PRNGs, but its widely understood a PRNG that passes any number of properties does not guarantee randomness. have you read the paper? another consideration is generation time; PRNGs "quality" comes at the expense of run time. there is no "preferred" or "ideal" PRNG and its presumably "working as advertised..." "snake oil" sounds like an unfair/ overblown accusation not very professional in a scientific context... $\endgroup$ – vzn Nov 29 '15 at 0:53
  • 2
    $\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
5
$\begingroup$

A recent paper by Vigna starts with an explanation of the history of Mersenne-Twister (MT), and why it has prevailed so far.

The original paper about the Mersenne Twister was published by Makoto Matsumoto and Takuji Nishimura in 1997 [22]. At that time, the PRNG had several interesting properties. In particular, it was easy to build generators with a very large state space, and the largest version with 19937 bits of state became very popular. More importantly, many techniques used in the Mersenne Twister influenced later development, and helped F2-linear techniques to recover from the bad fame that followed the “Ferrenberg affaire”. [9]

It is difficult for non-specialists to understand the intricacies of PRNGs, but period is easy to understand: the fact that the sequence generated would not repeat before 219937 − 1 32-bit integers had been emitted was met with enthusiasm, and quickly the Mersenne Twister was adopted as the standard generator in many environments. For example, the stock PRNG of the gcc compiler and of Python, as well of the Maple mathematical computing framework, is some version of the Mersenne Twister

The authors of MT also present the challenges of defining what is a good random number generator in their 2006 paper, Pseudorandom Number Generation: Impossibility and Compromise, which also argues in favour of using Mersenne Twister.

The original MT was not without issues. Perhaps the most troubling is that MT can go into a bad state for 100000s of numbers. This is more or less equivalent to the issue of correlated samples with close seedings. There is not a single MT, and more modern versions, such as Well19937a or Melg19997 have solved this issue.

Regarding state size or equivalently, memory consumption, this is partly an issue (does it make sense to worry about this for modern processors?). One can always use an MT with a smaller period such as Well512a or Well1024a. This period is still very large for practical applications.

Recently, Harase has shown some obvious linear relations present in the original Mersenne-Twister. This is in general less of a practical issue, and has again been addressed by the more recent Well or Melg algorithms.

Finally, while equidistribution looks like a nice property to have, with its connection to quasi Monte-Carlo simulations. It has obvious strong defects, stated in Vigna's paper above, and is not clear if it is desirable at all (see R.P Brent paper).

Good alternatives, although a little bit slower in general (but orders of magnitude faster to skip-ahead), are L'Ecuyer MRG32k3a (or the 53 bits version), or counter-based cryptographic generators such as AES (Intel and AMD processors have specific routine to generate those fast), or Salsa/Chacha possibly with fewer rounds. Some newer generators like Savvidy Mixmax-17, used for particle physics simulations in ROOT, look promising as well.

| cite | improve this answer | |
$\endgroup$
19
+100
$\begingroup$

The initial Mersenne-Twister (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.

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^{19937} - 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. Fails LinearComp Test of the TestU01 Crush and BigCrush batteries.
  • 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^{19937}$, 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.

| cite | improve this answer | |
$\endgroup$
  • 8
    $\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
  • 12
    $\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
  • 3
    $\begingroup$ "Predictable" -- MT isn't intended as a cryptographic PRNG so please edit your answer. $\endgroup$ – Jason S May 29 '17 at 16:55
  • 1
    $\begingroup$ "Mersenne Twister is not good enough anymore" : what is recommended if security is no concern, setting a seed is important and speed is important as well? (mersenne was fast enough) $\endgroup$ – Martin Thoma Nov 28 '19 at 14:31
  • 1
    $\begingroup$ Thanks @jherek. I'll take a look at the thesis. I'm not an expert on these matters, but as I understand it, it has to be the case that eventually, you'll get to a high-zero state simply because the numbers will repeat. Suppose you start with a seed with mostly zeros, and run for several ten-thousands of iterations, until you get to a balanced state. Now start over, but use that balanced state as your seed. Then within fewer than $2^{19937}-1$ iterations, you will come back to your original mostly-zeros seed. Of course, in practice, you are not going to generate that many numbers. $\endgroup$ – Mars Oct 9 at 6:51
14
$\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.

| cite | improve this answer | |
$\endgroup$
  • 7
    $\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
  • 1
    $\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
  • $\begingroup$ Also interesting would be to know your view on why MT prevailed over MRG32k3a given than one came out in 1998 and the other in 1999. Does it have some better equidistribution properties (esp. the Well variants)? Is it purely speed (MRG32k3a may be slightly slower)? On my MC simulations, it "looks" like the newer MTs give a result closer to the true result. A cryptographic RNG such as AES "seems" leads to results more often at the boundary of 3 std errors of the true result. Unfortunately I did not attempt to measure carefully this. $\endgroup$ – jherek Sep 12 at 10:08
7
$\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.

| cite | improve this answer | |
$\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
0
$\begingroup$

I produced now a simple overview of most of the known RNG's, with its speed and quality, based on improved dieharder tests.

https://rurban.github.io/dieharder/QUALITY.html

For TestU01 and PractRand results see the linked https://github.com/lemire/testingRNG overview, but yields the same results. You just need to wait days for the same results.

Best and fastest are: wyrand, xoshiro128+, xoroshiro64**, xoshiro128++, xoroshiro64*, lxm, efiix64 plus the slow threefry2x64.

MT comes out as good (1 major weakness), ranked as 10th of the good rng's. Note that the SIMD optimized sfmt comes out as bad, which could point to an implementation error.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ “TestU01 and PractRand results [...] but yields the same results”. Do they? The Mersenne Twister and several others you list fail PractRand. $\endgroup$ – Veedrac Nov 6 at 23:06
  • $\begingroup$ Yes. PractRand is a bit stricter. I meant more of less the same. dieharder has a WEAK category. $\endgroup$ – rurban Nov 8 at 20:39

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.