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.
That on its own requires prngs.
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...
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.
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.
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...
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.
and this matrix breaks it down well
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.
PCG = LGC + permutation
It is certainly the algorithm the author thinks we should use.
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
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.
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.
And I used an STM32G031, which doesn't have one.
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.
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.
I mostly agree though, the downsides are minor and/or rare if you aren't defending against attacks to the PRNG.
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.
> 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.
Care to square that circle?
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.
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).
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.)
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.
Note that the writer of this paper is a author of Xorshiro, so that might influence his recommendation.
She's also written several times about flaws in various xorshift/xorshiro-family RNGs, e.g.:
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.
The current #1 wyhash just released a newer, much faster version, which is not tested.
This is my overview over all known PRNG's:
This indicates a flaw in your testing methodology.
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.
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.
xor, shift, rotate vs. xor, rotate, shift, rotate
Xorshiro is either a mistake or an attempt to be clever...