9 ms·
It is high time we let go of the Mersenne Twister (2019)
- fancyfredbot 6y agoBut 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.
- Asooka 6y agoHm, "Mister G"?
- ajross 6y agoHad 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.
- josephg 6y agoMy new phone is faster than my current desktop CPU. Faster everywhere except in embedded applications is still pretty compelling!
- ajross 6y agoBut your thermostat is not, and it probably needs a PRNG too.
- quiescant_dodo 6y agoI'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.
- garmaine 6y agoMany boring, everyday algorithms employ random choice or blinded inputs to prevent worst case execution.
- alanbernstein 6y agoThough 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.
- 317070 6y agoWell, these days they are actually often connected to the internet. That on its own requires prngs.
- carlmr 6y agoI 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.
- raverbashing 6y agoSo it needs a PRNG, but not a cryptographically secure one
- deleted 6y ago[deleted]
- sdenton4 6y agoLuckily, if it's anything like MY thermostat, the detected temperature is itself a PRNG.
- antonvs 6y agoThe 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.
- GuB-42 6y agoIt 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.
- pkhuong 6y agomrg32k3a 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.
- loeg 6y agoPCG is the way to go. Small state requirements, very fast, good distribution: https://www.pcg-random.org/index.html https://www.pcg-random.org/index.html
- SeanLuke 6y agoPCG 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.
- loeg 6y agoThat’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.
- derbOac 6y agoThat'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.html 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).
- nsajko 6y ago> 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...
- throwaway_pdp09 6y agoGreat comment. In a world overrun by marketeers, polluted by image over substance, someone calls for more and on HN of all places.
- permo-w 6y agoI think the comment is meant to be joke expressing the exact concerns you are raising
- excitom 6y agoI 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.
- cirno 6y agoThis 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.
- hansvm 6y agoNot 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.
- ReactiveJelly 6y agohttps://www.datamation.com/entdev/article.php/616221/How-We-Learned-to-Cheat-at-Online-Poker-A-Study-in-Software-Security.htm 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.
- kazinator 6y agoInteresting 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.
- lifthrasiir 6y agoWhen 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/ https://github.com/KilledByAPixel/OS13k/
- Jasper_ 6y agoStrong 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.
- lifthrasiir 6y agoThat 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-number-generators/ https://chasethedevil.github.io/post/war-of-the-random-numbe...
- hatsunearu 6y agoYeah, 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
- MengerSponge 6y agoFun 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.
- RodgerTheGreat 6y ago"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.
- SethTro 6y agoPCG 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 https://www.youtube.com/watch?v=45Oet5qjlms&t=2s and this matrix breaks it down well https://www.pcg-random.org/index.html https://www.pcg-random.org/index.html
- Sharlin 6y agoLCG? 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.
- klodolph 6y agoI 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
- loeg 6y agopcg64_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-practrand.html https://www.pcg-random.org/posts/128-bit-mcg-passes-practran...
- lifthrasiir 6y agoI'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.
- klodolph 6y ago
- wnoise 6y agoSo, what should we be using instead?
- jeffbee 6y agoThe paper is a bit light on its recommendation, but it seems to favor xoshiro256++. Others might suggest Randen. http://prng.di.unimi.it/ http://prng.di.unimi.it/ https://arxiv.org/pdf/1810.02227.pdf https://arxiv.org/pdf/1810.02227.pdf
- ajross 6y agoYeah, 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.
- owenmarshall 6y ago> 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 https://en.m.wikipedia.org/wiki/Mersenne_Twister Care to square that circle?
- lifthrasiir 6y agoThe 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.
- 6y ago
- pps43 6y agoI'm using quasi-random generators where I can, and MCG 128 where I can't.
- ilaksh 6y agoDoes numpy have a good new random generator? Or what is good for Python?
- nimih 6y agonumpy 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 https://numpy.org/devdocs/reference/random/index.html
- ncmncm 6y agoVarious 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?
- cozzyd 6y agoXoshiro 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...
- slmjkdbtl 6y agoIs there any use cases for high quality PRNG for anything other than encryption? The simplest 3 line LCG seem to fit in most cases.
- mdouglass 6y agoIn 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.
- slmjkdbtl 6y agoIf 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.
- aquarin 6y agoMonte Carlo simulations.
- pvitz 6y agoDepends 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.
- rurban 6y agoAgreed. 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 https://rurban.github.io/dieharder/QUALITY.html
- CodesInChaos 6y agoHow 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.
- thraway123412 6y agoRandom 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.
- rurban 6y agoNo, different testing strategy. See https://github.com/rurban/dieharder/issues/6 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.