The war of the random number generators

These days, there seems to be some sort of small war to define what is a modern good random number generators to advise for simulations. Historically, the Mersenne-Twister (MT thereafter) won this war. It is used by default in many scientific libraries and software, even if there has been a few issues with it:

  1. A bad initial seed may make it generate a sequence of low quality for at least as many as 700K numbers.
  2. It is slow to jump-ahead, making parallelization not so practical.
  3. It fails some TestU01 Bigcrush tests, mostly related to the F2 linear algebra, the algebra of the Mersenne-Twister.

It turns out, that before MT (1997), a lot of the alternatives were much worse, except, perhaps, RANLUX (1993), which is quite slow due to the need of skipping many points of the generated sequence.

The first issue has been mostly solved by more modern variants such as MT-64 or Well19937a or Memt19997. The warm-up needed has been thus significantly shortened, and a better seed initialization is present in those algorithms. It is not clear however that it has been fully solved, as there are very few studies analyzing the quality with many different seeds, I found only a summary of one test, p.7 of this presentation.

The second issue may be partly solved by considering a shorter period, such as in the Well1024 generator.

The third issue may or may not be a real issue in practice. Those tests can be seen as taylored to make MT (and F2 algebra based generators) fail and not be all that practical. However, Vigna exposes the problem on some more concrete examples in his recent paper. The title of this paper has the provocative title It Is High Time We Let Go Of The Mersenne Twister. Before that paper, Vigna and her arch-enemy O’Neil, regularly advised to let go of the Mersenne-Twister and use a generator they created instead. For Vigna, the generator is some variant of xorshift, the most recent being xoroshiro256**, and for O’Neil, it is one of her numerous PCG algorithms. In both cases, a flurry of generators is proposed, and it seems that a lot of them are poor (Vigna criticizes strongly PCG on his personal page; O’Neil does something similar against xorshift variants sometimes with the help of Lemire). The recommended choice for each has evolved over the years. For a reader or a user, it looks then that both are risky/unproven. The authors of MT recently also added their own opinion on a specific xorshift variant (xorshift128+), with their papers Again, random numbers fall mainly in the planes: xorshift128+ generators and Pseudo random number generators: attention for a newly proposed generator. An important insight of that latter paper, is to insist that it is not enough to pass a good test suite like BigCrush for a generator to be good.

So what is recommended then?

A good read on the subject is another paper, with the title Pseudorandom Number Generation: Impossibility and Compromise, also from the MT authors, explaining the challenge of defining what is a good random number generator. It ignores however the MRG family of generator studied by L’Ecuyer, whose MRG32k3a is also relatively widely used, and has been there for a while now without any obvious defect against it being proven (good track record). This generator has a relatively fast jump-ahead, which is one of the reasons why it regained popularity with the advent of GPUs and does not fail TestU01 BigCrush. It is a bit slower than MT, but not much, especially with this implementation from Vigna (3x faster than original double based implementation).

There are not many studies on block based crypto-generator such as AES or Chacha for simulation, which become a bit more trendy (thanks to Salmons paper) as they are trivial use in a parallel Monte-Carlo simulation (jump-ahead as fast as generation of one number). In theory the uniformity should be good, since otherwise that would be a channel of attack.

The conclusion of the presentation referenced earlier in this post, is also very relevant:

Comments

comments powered by Disqus