It is high time we let go of the Mersenne Twister (2019) | Hacker News Reader

It is high time we let go of the Mersenne Twister (2019)

arxiv.org

162 pointshenning92 comments

But it has such a cool name! Sure mrg32k3a has a smaller state, runs faster and has a quick skip ahead function but L'Ecuyer just didn't put enough effort into the marketing.

Hm, "Mister G"?

Had to look it up to check, but it's not marketing. That function is part of a family that requires double precision floating point. So "runs faster" is a bit spun relative to a 32 bit integer function. Sure it does, on your desktop CPU.

My new phone is faster than my current desktop CPU. Faster everywhere except in embedded applications is still pretty compelling!

But your thermostat is not, and it probably needs a PRNG too.

I'm honestly curious why any non-smart thermostat would need a PRNG. Can you give examples why it would be needed?

I'm assuming my thermostat is a input-output machine where the input is detected ambient temperature (computed internal to the device) and the output is either RUN_FURNACE or DO_NOT_RUN_FURNACE.

Many boring, everyday algorithms employ random choice or blinded inputs to prevent worst case execution.

Though I'm sure that's true, a simple thermostat can be built without any electronic components at all, using only the simplest of analog mechanisms, so it's hard to see how it's relevant.

Well, these days they are actually often connected to the internet.

That on its own requires prngs.

I think the point was that if they're fast enough to connect to the internet they will be fast enough to calculate PRNGs. If they're not connected to the internet, they don't need them.

So it needs a PRNG, but not a cryptographically secure one

Luckily, if it's anything like MY thermostat, the detected temperature is itself a PRNG.

The idea of a thermostat using its own detected temperature as a random input to help set the temperature would be horrifying, if I weren't already convinced that that's how mine works.

It is actually a true RNG. Thermal noise, or whatever is messing up with your thermostat can be used as a source of entropy by hardware RNGs.

mrg32k3a uses double float for integer arithmetic because it was designed (like poly1305) back when computers were mostly 32 bit, and C compilers didn't reliably expose 64 bit operations. It's easy to implement with 32-bit integer arithmetic in assembly, and trivial in C with 64-bit integers.

PCG is the way to go. Small state requirements, very fast, good distribution:

https://www.pcg-random.org/index.html

PCG has had no peer review of its author's claims at all, and some of those claims are dubious. PRNGs are serious things and require serious deliberation.

That’s not true? BigCrush and PractRand results have been (trivially) reproduced, performance is also easy to verify. What claims are dubious? Everything about PCG strikes me as serious and deliberate.

That's not technically true. The history of the peer review process is outlined here:

https://www.pcg-random.org/posts/history-of-the-pcg-paper.ht...

I'm confused about why the author didn't just resubmit it elsewhere, but to me PCG as an example raises a lot of questions about the value of peer review today, and about how it is conducted (not that I think it does or doesn't have value, but it raises a lot of questions about it). At least from the author's perspective it seems the concerns were about presentation rather than substance. Speaking from personal experience, peer review can be quixotic and I put little weight on it not appearing in a peer-reviewed journal, as opposed to any specific criticisms that might have been raised in a review (given the attention to PCG at this point, if there were serious criticisms of it it seems a failing on the part of the journal not to address these).

> That's not technically true.

So your argument is that rejection from peer-review counts as peer-review?

> I'm confused about why the author didn't just resubmit it elsewhere [...] concerns were about presentation rather than substance

As far as I understand, the PCG paper is double the size it should be to get accepted by a serious journal. It contains a lot of unnecessary explanations of basic facts, making it unnecessarily tiresome to read for an expert. Presentation matters, because it stands between you and the substance, and you have to be able to get to the substance as fast as possible to review the paper.

> [...] (given the attention to PCG at this point, if there were serious criticisms of it it seems a failing on the part of the journal not to address these).

Well, the paper was rejected before it could come to that point...

Presentation does matter, but is the least important part and the most changeable. In this case it is also the part that has nothing to do with the actual performance of PCG.

I think she should have resubmitted it, but I think it says volumes about the problems of peer review that PCG is a widely known algorithm, widely discussed, and yet here we are discussing the merits of a particular presentation of it, as perceived by a couple of unknown persons.

I'd much rather have this HN discussion focused on open assertions of problems with PCG and rebuttals.

> I think she should have resubmitted it, but I think it says volumes about the problems of peer review that PCG is a widely known algorithm, widely discussed

PCG is only "widely discussed" because its inventor has personally and very heavily promoted it.

We only have the author's side of the story regarding the review. That it wasn't resubmitted for peer review is a huge red flag. The author has also publicly dismissed (what appears to me to be) valid and well-founded criticism of the algorithm, and made some unsubstantiated and one-sided charges about the academic peer review process. This has more than a faint odor of quackery about it, and that's not good about something as fundamentally important as a PRNG.

You're kind of confusing different issues.

On the one hand, PRNGs aren't a very popular research subject AFAIK. The Blackman/Vigna PRNGs (which are the other recently popular PRNG family) likewise only got papers on Arxiv, AFAIK; so it's not clear to which peer-reviewed PRNG are you comparing PCGs. We are talking about non-crypto PRNGs here after all, which mostly get tested just experimentally, to check their statistical quality.

On the other hand, there is a really weird claim associated with the PCG family: that it is challenging to predict and that it thus "provides many of the benefits provided by CSPRNGs". This is how the PCG designer ends the abstract of her PCG paper:

> These functions can be designed to make it difficult for an adversary to discover the generator’s internal state by examining its output, and thus make it challenging to predict. This property, coupled with the ability to easily switch between random streams, provides many of the benefits provided by cryptographically secure generators without the overheads usually associated with those generators.

That's baloney. PCGs are not CSPRNGs, but she's deceptively trying to make it sound like they kind of are (have the same benefits). Anyway, a relatively efficient attack has been demonstrated this year: https://hal.inria.fr/hal-02700791/

Another issue with the "challenging predictability" design goal is that it seems to come at the cost of necessary trade-offs at the expense of speed and/or statistical quality, even though it is of dubious utility (considering that no real guarantee is given, and that a relatively efficient attack has recently been demonstrated): https://github.com/numpy/numpy/issues/16313#issuecomment-726...

I think you might be responding to someone else's posting? Not that I disagree with what you said.

My point was that PRNGs like the PCG family don't get peer-reviewed anyway (if they're not meant as CSPRNGs), although the way PCGs were presented is problematic because the author lays claim to "many of the benefits" of CSPRNGs, which would require peer-review for a start to be taken seriously.

Also, to be clear I suppose that using a PCG is a fine choice for, e.g., a simulation; just don't rely on it being "challenging" to predict.

The author of PCG published a new member of the family on her Github in 2019. There was no blog post and I think the only announcement was on a certain Numpy Github issue, but the DXSM variants are supposed to be faster and have even better statistical qualities according to the relevant empirical tests, as well as being immune to some of the peculiarities of the earlier PCG schemes. Here's the commit: https://github.com/imneme/pcg-cpp/commit/871d0494ee9c9a7b7c4...

Great comment. In a world overrun by marketeers, polluted by image over substance, someone calls for more and on HN of all places.

I think the comment is meant to be joke expressing the exact concerns you are raising

PCG and LCG (permuted/linear congruential generator) seem much stronger. This is one of my favorite presentations on the subject https://www.youtube.com/watch?v=45Oet5qjlms&t=2s

and this matrix breaks it down well https://www.pcg-random.org/index.html

LCG? Really? Mersenne Twister originally became the cool kid because LCG's are so bad. Well, at least your standard issue `rand(3)` implementations tend(ed) to be.

I think the comment mentions LCG because it’s the basis for PCG, not because you should be using an LGC by itself.

PCG = LGC + permutation

pcg64_fast is a plain MCG (which are a subset of LCGs), and 128-bit MCGs have perfectly good statistical properties:

https://www.pcg-random.org/posts/128-bit-mcg-passes-practran...

I'm less sure about the terminology, but shouldn't we distinguish truncated LCGs from untruncated (plain) LCGs? It is clear that untruncated LCGs have very predictable lower bits by the definition and don't have "perfectly good statistical properties" by its own (it would have been fine if untruncated LCGs weren't wildly popular though). One of PCG's biggest contributions to me is a distinct name given to LCG plus tampering so that we can avoid the ambiguous "LCG" label.

Yeah, I’d think if I had to sit down and write a definition for LCG, it would just be X_(n+1) = (a X_n + c) mod m. Since we’ve discovered “high bits good, low bits bad”, we can create generators that are based on LCGs but either throw away the low bits or mix them in. I don’t know if I’d call them LCGs, though.

Sure; to be very clear, it’s 128-bit state, 64-bit range LCGs which have great properties.

Yes, 128-bit LCGs with well-chosen constant(s) are fast as hell and pass all statistical tests (you don't even need the addition factor, a good multiplier works too ("MCG")):

https://www.pcg-random.org/posts/does-it-beat-the-minimal-st...

The rand(3)s were crap because they were ~32-bit LCGs with a ~32-bit output size. You need 96-128 bits of state for a 32-64 bit output LCG.

Thanks, interesting!

The author of the paper is the author of Xoroshiro:

https://en.wikipedia.org/wiki/Xoroshiro128%2B

It is certainly the algorithm the author thinks we should use.

Strong agreement. xorshift or even a basic LCG work far better than Mersenne Twister. The only reason MT has persisted in the public consciousness for so long is because it has a memorable and cool name.

Yeah, I was making a Nixie tube clock with an STM32 and I was debating what I should use for my RNG...

I was trying to write a decent implementation for a LFSR PRNG and my friend was like fuck that, STM32 has a HW multiplier, just use an LCG and I wrote one from memory with like 2 lines. Just needed to grab the magic constants from wikipedia... (which I needed to anyway if I wanted to use an LFSR)

Strongly recommended, if you don't care about quality, LCG is simply unbeatable in terms of quick n dirtiness

Fun little bit of computer history: the Atari game "River Raid" (available on some flashback consoles) uses "randomly" generated landscapes and obstacles, but it's exactly the same every time you play it.

It uses the same seed on its LCG when you start the game, so everything else is deterministic. As far as I know it's the first procedurally generated video game.

"Pitfall" for the Atari 2600 uses the same approach for laying out obstacles, with a carefully tuned seed that produces a winnable game world with reasonable difficulty progression.

Another 2600 game, "Entombed", has seen recent enthusiasm for a novel automata which generates aesthetically pleasing and mostly-solvable mazes with a minimum of working memory.

Rogue is two years older than River Raid and also used procedural generation.

Which STM32 part? Some of them have a hardware RNG.

Yeah, but an LCG is easier ;P

And I used an STM32G031, which doesn't have one.

That sounds like a stretch. MT got its fame when LCG is the most popular PRNG in the world, and being the first popular PRNG that is measurably better than LCG did help. In fact the current "war" of PRNGs [1] hinders the adoption of both competing generators because MT is still good enough (in spite of its known throughput issue) and people doesn't like the choice.

[1] https://chasethedevil.github.io/post/war-of-the-random-numbe...

The large period is a certainly a desirable property when you are going to be drawing a few billion numbers.

It is also easy to port to different languages.

Interesting mentions of the WELL family. I chose WELL512 for TXR Lisp back in 2011.

Unfortunately, the implementation was bungled until October 2020. :(

If you re-implement, don't be a cowboy: validate that you're getting identical results to the reference implementation.

When I was helping the development of OS13k [1] I found that the ported JS version of xorshift32 was incorrect (right shift was sign-extended instead of zero-extended). I had to run TestU01 to ensure that it's not noticably made worse (and thankfully it didn't).

[1] https://github.com/KilledByAPixel/OS13k/

I was developing casual games (Backgammon, Spades) around the time the Mersenne Twister came out and it looked new and shiny and cool so I adopted it for my random number generator. I ran 10s of millions of dice rolls and card shuffles through it and the results seemed good. Oh well.

This only matters for things like encryption and secrets. Imagine if you published your game online as multi-player, someone could devise the randomness and predict the next moves in the game, which could allow them to cheat. For encryption, a predictable RNG can break the entire scheme.

In your casual sense of just a single-player game, there's no harm, but the idea in replacing MT with something like PCG is to be more secure/safe by default, since you never know what someone will use rand() for.

Not just that, but their game is mildly more resource hungry than it could be because of the large MT state space, and depending on the exact nature of how many rolls/cards are expected per game and what is done with them MT could yield "unnatural" games at a highly elevated frequency which might play significantly differently from a physical counterpart.

I mostly agree though, the downsides are minor and/or rare if you aren't defending against attacks to the PRNG.

https://www.datamation.com/entdev/article.php/616221/How-We-...

> recall that the seed for a 32-bit random number generator must be a 32-bit number, meaning that there are just over 4 billion possible seeds. Since the deck is reinitialized and the generator re-seeded before each shuffle, only 4 billion possible shuffles can result from this algorithm. Four billion possible shuffles is alarmingly less than 52!.

> To make matters worse, the algorithm of Figure 1 chooses the seed for the random number generator using the Pascal function Randomize(). This particular Randomize() function chooses a seed based on the number of milliseconds since midnight. There are a mere 86,400,000 milliseconds in a day. Since this number was being used as the seed for the random number generator, the number of possible decks now reduces to 86,400,000. Eight-six million is alarmingly less than four billion. But that's not all. It gets worse.

That article was rife with errors. Notably "recall that the seed for a 32-bit random number generator must be a 32-bit number" is quite obviously wrong, the seed size is constrained by the generator's state size, not its output size.

MT isn't really bad in any sense, except if you're in a ridiculously memory-constrained environment (or just have tens of thousands of concurrent generators) and 2 kB of state is too much.

So, what should we be using instead?

The paper is a bit light on its recommendation, but it seems to favor xoshiro256++. Others might suggest Randen.

http://prng.di.unimi.it/

https://arxiv.org/pdf/1810.02227.pdf

Yeah, the xorshiro family are the current cool kids.

But really: use whatever your library provides. Despite the protests in the article, MT is just fine. It's not slow. It's state requirements are not that high. It's quality is not actually bad in any way that typical applications (yes, even crypto) care about.

This is a mature area. It's last revolution was more than two decades ago when we walked away from LCRNGs, and frankly not much has really changed since.

It's not worth your time. But yeah, if you have to pick something pick xorshiro.

> It's quality is not actually bad in any way that typical applications (yes, even crypto) care about.

> observing a sufficient number of iterations (624 in the case of MT19937, since this is the size of the state vector from which future iterations are produced) allows one to predict all future iterations.

https://en.m.wikipedia.org/wiki/Mersenne_Twister

Care to square that circle?

The MT19937 state is a batch of 624 32-bit numbers which gets tampered and returned by the generator in the order. The tampering function is invertible, so each group of 624 successive numbers directly corresponds to the state.

State extraction is possible with all RNGs to varying extents. These are not stream ciphers. Good seeding remains important always, and that's part of the crypto protocol, not the RNG. This is not a problem for using MT responsibly in things like key generation, etc...

Again: don't sweat this. If you are competent to write your own crypto code and have a good argument for xorshiro or whatever, then use that. If you just need a random number for whatever reason, use your library and don't bother with the advice in the linked article.

Good libraries have more than one random number generator.

Yes, use your library if you are not competent to write your own or don't want to, but use the right library function.

For example don't use random.randint() in Python if you need a random integer for crypto. Use random.SystemRandom().randint(). The former uses Mersenne Twister and is predictable. The latter uses os.urandom() for its underlying random bytes, which uses an OS-specific random source (/dev/urandom on Unix and Unix-like OSes) and should be sufficiently unpredictable for all cryptographic uses.

There is also the secrets library in Python 3.6 and later. It's not better than random.SystemRandom, it's just a different interface to the OS secure random number generator. If you want your code to work unmodified on Python before 3.6 it is fine to use random.SystemRandom (or if you like its interface more).

> For example don't use random.randint() in Python if you need a random integer for crypto.

If you need a random number "for crypto", you should be using a crypto library's key generation function or whatever. What you describe is writing a crypto protocol, and that's way out of the realm of discussion here. (But yes: you don't naively use a PRNG of any type for that. The SystemRandom() utility hooks the OS entropy pool.)

There are situations where the Pyhton random module can provide easy API for cryptographically unpredictable events.

E.g. you can pick random words for passphrase from wordlist with random.SystemRandom().choice(word_list). SystemRandom is a CSPRNG. It's of course incredibly dangerous that you can accidentally use MT by forgetting to put in the SystemRandom() part. random.choice(word_list) works as well and doesn't fail tests.

It would be really important to make all RNGs cryptographically secure unless explicitly stated that the RNG must be very fast at the cost of predictability, and the naming should reflect that, e.g. insecure_scientific_random.randint() for Monte Carlo simulations etc.

GP is just wrong (or misspoken); MT should not be used for cryptographic purposes.

The two most recommended options are variants of Xorshiro and PCG. There's a small comparison of the options in Rust's rand crate which I assume is neutral here: https://rust-random.github.io/book/guide-rngs.html

Note that the writer of this paper is a author of Xorshiro, so that might influence his recommendation.

Similar comparison from the author of the PCG family:

https://www.pcg-random.org/posts/other-good-options.html

She's also written several times about flaws in various xorshift/xorshiro-family RNGs, e.g.:

https://www.pcg-random.org/posts/xoshiro-repeat-flaws.html

https://www.pcg-random.org/posts/implausible-output-from-xos...

https://www.pcg-random.org/posts/a-quick-look-at-xoshiro256....

https://www.pcg-random.org/posts/xoroshiro-fails-truncated.h...

PCG. Small state requirements, very fast, very good distribution: https://www.pcg-random.org/index.html

The author of the paper is the author of Xoroshiro128+

https://en.wikipedia.org/wiki/Xoroshiro128%2B

I'm using quasi-random generators where I can, and MCG 128 where I can't.

Is there any use cases for high quality PRNG for anything other than encryption? The simplest 3 line LCG seem to fit in most cases.

In games it is definitely nice to have. I’ve built multiple online trading/collectible card games and it’s a necessity for those. Don’t want your players predicting what cards will be drawn/in what order.

If the game deals with real world currency I can see why it's important, but if it's casual I'd say players trying to predict card is a very fun puzzle game on its own, imagine the intensity of a PvP card game where both player are playing cards against each other but at the same time trying to decode the PRNG algorithm, that's some quality emergent gameplay right there.

Monte Carlo simulations.

Depends on the type of the simulation, but quite often, low discrepancy numbers (like Sobol sequences) are the better choice. Especially in finance, good engines don't or rarely use random numbers.

PRNG are used for MC in both finance and physics.

I agree, but I wrote "good engines". If one can choose between convergence with 1/N over 1/sqrt(N), the choice shouldn't be difficult especially in real-time systems.

Try http://extremelearning.com.au/unreasonable-effectiveness-of-...

MC simulations, used for things like rendering (path tracing) in the CG/VFX industry. Having very good distribution and a large period are quite important, given how many random numbers (often billions, for every path bounce, light sample, camera position for pathtracing) are required amongst many dimensions.

Not many, apart from GPU/CUDA. This is why so few researchers work in the area, and why they are so hostile to each other: they are protecting their small, remaining turf.

All desktop CPUs made after 2010 provide blazing fast AES instructions (and on the mobile side, even ARMv8-a, from 2011, had them). Running AES in counter mode provides deterministic, high quality pseudo-random numbers faster than any of these proposed PRNGs.

Even if someone ends up in the unlikely situation where RNG throughput is the bottleneck in their Monte Carlo algorithm (which implies that they do pretty much no computation other than generating random numbers; having worked in a search- and genetic-algorithms-heavy field before the AI/GPU craze, I've personally never seen it happen), they'll be much better off getting a non-ancient CPU and switching to AES than trying to use any of these generators.

Image processing. If you want to dither or you want to generate noise, you don't want there to be obvious repeating patterns. Weird things can happen like the period being exactly an integer number of pixels that also happens to line up on a frame boundary, so every n frames the pattern repeats. I've had to fix things like this in the past.

Agreed. We should use better and faster PRNG's.

The current #1 wyhash just released a newer, much faster version, which is not tested.

This is my overview over all known PRNG's: https://rurban.github.io/dieharder/QUALITY.html

How did AES-OCB, Threefish-OCB and Chacha end up in the weak list? Since they're all unbroken stream ciphers, I have a hard time believing the tests uncovered a genuine weakness.

This indicates a flaw in your testing methodology.

Random chance. Even the most secure generator (or true randomness) will generate "weak" results with dieharder if you run it a few times.

Dieharder is useless for everything except spotting obviously and blatanly broken RNGs. Also, dieharder (like all other statistical tests) make absolutely no statement about security. A generator that scores high may be trivial to predict.

It's also worse than PractRand or TestU01. Generators that score consistently well on dieharder can fail predictably and consistently PractRand and TestU01 (because the generator has actual flaws that Dieharder cannot detect but the others can). I don't see any reason to use Dieharder at all, it's ancient and has not been relevant for a long time.

No, different testing strategy. See https://github.com/rurban/dieharder/issues/6

You could remove outliers which occur statistically with a certain chance, cry out at the first encounter, or check weak results again with different seeds to resolve potential ambiguities in bad p-values.

With my fixes dieharder finds the same flaws as PractRand and TestU01, just faster. PractRand is still better though.

The cited crypto generators are not statistically better, as they fail much more tests then expected. They are just more secure. More secure does not mean that it is better per se.

The security definition for RNGs is indistinguishably from truly random data. So if there is any test that they fail more often (averaged over random seeds) than true randomness, they're broken.

So you're claiming that dumb statistical tests broke three completely different CSPRNGs? That's a rather extraordinary claim, which I have a hard time believing.

There is no such thing as "not statistically better, just more secure" [1]. If an AES DRBG systematically fails your statistical test, then something is wrong. Probably your DRBG implemetation, or your test.

[1] https://en.wikipedia.org/wiki/Distinguishing_attack

Various remarks recommend "xorshiro", but the paper linked says "xoshiro/xoroshiro". Is the first an abbreviation to refer to both of the second? Or just inattention to detail?

Xoshiro and Xoroshiro are slightly different methods, named after the operations used.

xor, shift, rotate vs. xor, rotate, shift, rotate

Xorshiro is either a mistake or an attempt to be clever...

Does numpy have a good new random generator? Or what is good for Python?

numpy currently uses PCG64 by default[1]. The python standard library uses a version of the Mersenne Twister.

[1] https://numpy.org/devdocs/reference/random/index.html

Reply on news.ycombinator.com