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.
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.
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.
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.
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.
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.
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.
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...
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.
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).
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.
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.
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...
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.
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.
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")):
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.
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.
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.
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.
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).
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.
> 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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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?
