Mersenne Twister Considered Harmful
Written by Mike James   
Wednesday, 16 October 2019

The Mersenne Twister is a very common random number generator. It is used in C, Python, Mathematica, Excel, PHP, Ruby ... A new paper suggests it shouldn't be.

Random Number

xkcd

More cartoon fun at xkcd a webcomic of romance,sarcasm, math, and languag

The quality of the pseudo random numbers we use is important and the adoption of the Mersenne Twister generator, which is a special case of an F2 linear generator, was partly in response to the discovery that the current generators were flawed. As a new research paper by Sebastiano Vigna, inventor of xorshift+ and xoroshiro128+ used in the JavaScript engines of Chrome, FIrefox and Safari, says:

"Once language implementors decided to use the Mersenne Twister, the choice was doomed to be cemented for a very long time. Also, the problems of the Mersenne Twister are not immediately detectable in everyday applications, and most users really interested in the quality of their PRNG will make an informed choice, rather than relying on the stock PRNG of whichever programming environment they are using. So there was no strong motivation to move towards a better PRNG."

Part of the argument for not moving from the Mersenne Twister is that the tests it did fail were not important in the real world use of the generator. In particular, if you take the bits generated as uniformly distributed in the interval 0 to 1 and then apply a non-linear transformation to a different distribution then the defects go away. This is indeed the way that many simulations use pseudo random numbers but the new paper gives examples where this is not the case.

The bottom line of all of these examples is:

"F2-linear generators fail statistical tests which can have an impact on actual applications. They should be used with care, and only in context where there it is certain that strongly nonlinear operations will be applied to their output, so their defects are diluted or completely hidden. In particular, linear generators should never be used as general-purpose generators, unless their output is suitably scrambled by combining it with other, nonlinear generators, or by applying nonlinear maps. The current, dangerous ubiquity of the Mersenne Twister as basic PRNG in many environments is a historical artifact that we, as a community, should take care of. Moreover, several touted advantages of the Mersenne Twister, such as reparameterization, do not actually work properly when examined closely."

There also seems to be an easy fix to the problem - the use of a scrambler as in the author's own xoshiro256++ means that we have a generator which does not fail any known statistical test. The point is there are better ways of doing the job and we are not using them.

 dice

More Information

It is high time we let go of the Mersenne Twister

Related Articles

Neural Networks Learn to Produce Random Numbers

ERNIE - A Random Number Generator

Inside Random Numbers       

How not to shuffle - the Knuth Fisher-Yates algorithm

The Monte Carlo method

Canada's RAND Immigration Lottery Not Random!

Random Means Random - The Green Card Fiasco

Randomness Restored In Chrome 49

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on, Twitter, Facebook or Linkedin.

 

Banner


Go.Dev Portal Now Online
14/11/2019

A new portal for Go developers has been launched by the Go Developers Network. Go.dev is described as providing learning resources to get started with the language, featured use cases, and case studie [ ... ]



Cyber.dic - Spellchecking For Tech Terms and Acronyms
25/10/2019

Tired of your word processor red squiggling perfectly acceptable technical terms and acronyms? The cyber.dic spellcheck dictionary puts an end to that! 


More News

graphics

 



 

Comments




or email your comment to: comments@i-programmer.info

 

 

Last Updated ( Wednesday, 16 October 2019 )