A Family of Better Random Number Generators | Hacker News Reader

A Family of Better Random Number Generators

pcg-random.org

163 pointsmarcobambini118 comments

Xoshiro over PCG arguments: http://pcg.di.unimi.it/pcg.php

Response by the author: https://www.pcg-random.org/posts/on-vignas-pcg-critique.html

Personally, I use a SIMD Xoshiro256+ when I want a solid and fast RNG (although I mostly use Julia's default -- a MersenneTwister).

Thanks for digging this up. I was curious about exactly this.

Why does Julia use Mersenne Twister as default? I gather that it's quite bad by modern standards?

It _has_ a cool name, tough...

And the pcg page has pretty colors

"quite bad" is quite an overstatement; its quality isn't a problem for many real use cases. It's quite slow compared to the likes of PCG though.

Julia uses dSFMT, which is as fast as xoshiro on vigna own benchmark page. I would not call that slow.

Right, a bad phrasing from my part; I didn't actually mean the distribution, but more like... the bang for the buck. Why would you use slow generator as a default, if you don't even get good distribution?

You get a good distribution in 99.99% of the cases. There is no perfect rng. I am sure that pcg and xoroshiro also have deficiencies. The issue of good seedings is quite general.

Of course there are perfect RNG's. Some of them even quite fast. Good PRNG's eg. do have no seeding problem as most bad LCG's.

Some people are easy to satisfy I guess

It is very bad. It's is huge, 10x slower than good LCG's, and fails statistical tests, esp. it's lower bits, most wellknown by the Ferrenberg affair. https://arxiv.org/pdf/1910.06437.pdf

PCG is also not that good. There do exist proper and fast PRNG's though. DSFMT has the same problems as MT. I'm just adding some of them to gsl and dieharder btw.

Thank you for the reference. I stand corrected. I wasn't aware that its quality problems are that bad.

What's the best argument against PCG?

Give me a bit more time. I just added all the relevant modern RNG's to dieharder and am running all the tests. TestU01 later. Actually MT looks good enough to me now.

Preliminary results at https://github.com/rurban/dieharder/blob/pcg/QUALITY.md

Re PCG: statistical weaknesses compared to the good xoshiro's or wyrand, and much slower. I'm still missing SFMT (2x faster, due to simd), and the 2 newer PCG's with a good and a fast mixer.

But given the current results, there are a few new PRNG's which are so much better and faster than everything else: wyrand, xoshiro128+, xoroshiro64, xoshito128++, xoroshiro64

This is interesting. By the way, it is noticeable that Ferrenberg himself did not find anything wrong with MT in one of his latest papers. He however mostly used MRG32k3a, and checked that MT gave similar numbers.
https://arxiv.org/pdf/1806.03558

If you read that paper you referenced, the Mersenne-Twister actually ended the Ferrenberg affair. And where does it say that lower bits of dSFMT are bad? Is there proof for this statement? Now I am not saying that dSFMT is the best RNG ever, far from it. It's just very decent, and quite fast.
LCGs have an awkward habit of bad projections in 2D.

no, it is pretty good rng, but quite slow, and world move on since 80s

I can't tell you why it was originally chosen, but there is a PR underway to have tasklocal RNG in Julia. That necessitates a smaller RNG, and we'll probably land on xoshiro256
Ref: https://github.com/JuliaLang/julia/pull/34852

That response by O'Neill is amazing. Solid analysis and response. Staying away from name calling, and actually getting new results and knowledge out of it all. It even ends with a thank you to Sebastiano Vigna.

Definitely. Once the AVX512-IFMA instruction set becomes more common (only available on Intel 10nm CPUs so far), I may try a PCG with 104 bits of state. Wanting SIMD rngs (separate generator per vector lane), PCG is hurt by 64-bit integer multiplication being on the slower side. AVX2 has to perform three 32 bit multiplications, while the AVX512 instruction has much lower throughput than the likes of a xor, shift, or floating point arithmetic. The new IFMA may change that.
My use cases are Monte Carlo, where "passes statistical tests" is probably all that's needed for good results. Maybe I should just try an mcg.

For a view less centered on the pcg vs xoshiro world:
https://chasethedevil.github.io/post/war-of-the-random-numbe...

I used PCG years ago for procedural content generation where random number generation was a bottleneck. It is very fast, so I was happy with it. Additionally the implementation I used[1] is comprehensible enough that I could modify it in various small ways.
One property I anecdotally observed about it is that it is a little sensitive to the values you choose for its seed. Too many zero bits or making two generators with nearly-identical seeds would create visible correlation in the outputs. It worked much better if all values were hashed before using them for seeding.
[1] https://github.com/tlauterbach/unity-pcg-csharp

The website does not seem to have been updated but the prediction security of PCG has been fully broken recently (and does not rely on the "Challenging" part of the spectrum): https://hal.inria.fr/hal-02700791/
Hence any cryptographic use of PCG is definitely prohibited

Interesting that the strongest variant took an average 20,000 CPU-hours to break- so definitely not cryptographic strength, but not a walk in the park either.

20,000 core-hours is, what, a couple hundred bucks?

I'd call that a walk in the park if security is concerned.

This despite the extremely misleading green "Challenging" grade the authors gave PCG's security on their website.

On random numbers, I found the ideas behind "Parallel Random Numbers: As Easy as 1, 2, 3" [0] (which is implemented in JAX) interesting. Their generator is a mapping between keys and random numbers which get rid of the sequential dependency in the generator making it very easy to run in parallel at a GPU scale.
[0]: http://www.thesalmons.org/john/random123/papers/random123sc1...

I've been diving into parallel reproducible PRNG [1] in the end I choose to have a PRNG based on xoshiro and seeding process that could take loop iteration variables [2] for reproducibility:
- [1] https://github.com/mratsim/weave/issues/147
- [2] https://github.com/mratsim/trace-of-radiance/blob/99f7d85/tr...
- Usage for parallel raytracing: https://github.com/mratsim/trace-of-radiance/blob/99f7d85/tr...
Beyond the JAX paper, the Pedigree-based RNG from Leiserson was interesting as well:
- http://supertech.csail.mit.edu/papers/dprng.pdf
- https://pdfs.semanticscholar.org/a32c/3b7b8d5d3ebd594bea2d9c...
And Haskell's splittable RNG:
- http://www.hg.schaathun.net/research/Papers/hgs2015jfp.pdf
- http://publications.lib.chalmers.se/records/fulltext/183348/...
- http://gee.cs.oswego.edu/dl/papers/oopsla14.pdf

100% agree. You can also use chacha or aes the same way. I like it. I wonder however if some streams may not be too extreme with those.
https://chasethedevil.github.io/post/more-on-random-number-g...

Statistical Quality PCG Family Excellent ChaCha20 Good
What a joke.

The only complaint about ChaCha's statistical properties I could find on <https://www.pcg-random.org/other-rngs.html#id7> is:
> Fewer rounds result in poor statistical performance; ChaCha2 fails statistical tests badly, and ChaCha4 passes TestU01 but sophisticated mathematical analysis has shown it to exhibit some bias. ChaCha8 (and higher) are believed to be good. Nevertheless, ChaCha needs to go to more work to achieve satisfactory statistical quality than many other generators.

Exhaustive list of valid complaints about ChaCha (and CSPRNGs in general):
* too slow (for a scant few applications)
* too much state & code (for a scant few applications)
* can’t find a nice implementation (there are some, though)
Everything else written there is FUD. And this whole "statistical tests" thing is a red herring anyway. There’s a field that concerns itself with "statistical quality"—it’s called cryptography. They have plenty sophisticated mathematical analysis.

You might be surprised.
Cryptographic RNGs achieve their strength through large round-counts. ChaCha runs 20x quarter rounds of its algorithm, which means you're basically doing:
randomNumber = hash(hash(hash(hash...hash(seed)))))))))))
After 80-iterations of your hash function, you'd HOPE it was random looking!! In effect, cryptographic RNGs are built for safety, and have huge safety margins.
---------
The "natural" approach to making a non-secure (but faster) RNG is to reduce the hash rounds to a single cycle. IE: instead of running 80-quarter rounds of ChaCha, why not just run 1x quarter-round of ChaCha?
Well, it turns out that 1-round of ChaCha20 is utter crap. Completely crap, worse than a LCGRNG.
------
AES is similarly designed for 8+ rounds. In my experiments, it took 4 or 5 rounds before AES would achieve a decent distribution of bits!!
It took a fair bit of effort for me to turn AES into a random number generator. I analyzed AES's bit-flow, and designed a "counter function" that worked well with AES's single-round weakness. Even then, I never accomplished a 1-round of AES RNG, I had to use 2-rounds of AES to make a decent bit distribution.
In particular: 1-round of AES is only designed to shuffle bits across a 32-bit DWORD. You need the 2nd round (or more) to shuffle the bits to the whole 128-bit group. (That is: the "MixColumns" and "ShiftRows" step of AES, which only really take effect on the 2nd round or later).
-----
If anyone could figure out a special "seed" function that can work with AES's single-round weakness, they probably can make a much faster RNG than what I accomplished. Or maybe, people can just be "happy" with 32-bits of well-shuffled bits? A 32-bit RNG (with 128-bit seed) is probably still useful to somebody.

I’m not surprised; you’re rolling your own crypto.
Quoting JP Aumasson’s Too Much Crypto [0]:
The best result on ChaCha is a key recovery attack on its 7-round version, with 2^237.7 time complexity (the exact unit is unclear) using output data from 2^96 instances of ChaCha, that is, 2^105 bytes of data. On 6 rounds, a similar attack can run in time & data 2^116 & 2^116, or 2^127.5 & 2^37.5. On 5 rounds, the attack becomes practical due to the lower diffusion, and runs in 2^16 time and data.
You see what’s happening there? 5 rounds is easily broken, 6 rounds is borderline secure, 7 rounds is secure. Same thing with AES; these algorithms were never meant to be used the way you’re using them.
[0]: https://eprint.iacr.org/2019/1492.pdf

> I’m not surprised; you’re rolling your own crypto.
I agree! PRNGs are surprisingly difficult! The main difference I argue, is that the statistical-tests applied to crypto-algorithms are "harder" than the statistical-tests applied to PRNGs.
In a standard PRNG, you're happy if you can say pass the Chi^2 test. But with a Crypto-PRNG, you're aiming to beat differential cryptoanalysis.
What is differential cryptoanalysis? Well, its just a pair-wise statistical test across your bits!! Its a far more strict test than just Chi^2, but the overall concept is the same: Anything that differs from a uniform random distribution fails.
----------------------
> You see what’s happening there? 5 rounds is easily broken, 6 rounds is borderline secure, 7 rounds is secure. Same thing with AES; these algorithms were never meant to be used the way you’re using them.
Indeed. But for those who need "simple" PRNGs for simulation purposes.
Since PRNGs are designed for speed, their statistical tests are far easier than differential cryptoanalysis. You're "only" aiming for Chi^2, or other tests (See PractRand or BigCrush).
ChaCha over 5 or 6 rounds is going to be inevitably slower than a single-round of xorshift128!!
True, ChaCha "scales" to higher rounds (xorshift128 will probably fail differential cryptoanalysis even with 20+ rounds applied... while ChaCha continues to get "more secure" the more rounds you apply all the way up to 80+ rounds).
But that's a weakness PRNG users are willing to accept. As long as the bits are random enough for a monte-carlo simulation (for raytracing, or weather simulation, or... AIs), you're happy.
-----------
Because PRNGs tests are "easier" than crypto-tests, you can often make due with a single round alone. (See LCGRNG: a singular round of (seed = seed*K1 + K2) is sufficient to pass Chi^2 tests).
I've never designed a crypto-algorithm before. But based on my understanding of Crypto... the creation of PRNGs is a surprisingly similar field. GF(2), Bijections, mappings, bit-tests, statistical tests... they have applications to both crypto and PRNGs.

I don't think the comparison is really what it seems. We need to remember that PCG is not cryptographic, and thus I think the comparison is not meant to be ChaCha20, but more one of the ChaCha-versions that you would use in situations where you would use PCG. If you want chacha to produce random-looking data even nearly as fast as PCG does, you will need to run a lot fewer rounds. 8 rounds is, IIRC, about what you need for it to pass statistical tests, but if I would guess chacha8 would still be a lot slower than the better versions in the PCG family. If you want comparable speeds, you would need to run even fewer rounds, making the statistical quality even worse.

No. First of, they are explicitly comparing to ChaCha20.
Secondly, ChaCha1–7 aren’t a thing, outside of a cryptanalysis paper anyway. Primitives like ChaCha need a certain number of rounds to do what they do.
Finally, ChaCha8 doesn’t just “pass statistical tests,” it’s cryptographically secure.

Of course chacha1-7 is a thing. Just not for cryptography. I used 4 rounds of salsa to create random-looking numbers just for fun (4 rounds is what you need to get good diffusion), and I know for a fact that I am not alone in having the idea.
The reason nobody uses it like that is that it is slower than most other PRNGs

What applications require unpredictability where you wouldn't go full csprng?

Request back off / retries, any sort of simulation, various load balancing algorithms, randomized algorithms, fuzzing/testing, ...

Why does back off / retry require unpredictability?

To avoid a stampede of requests by synchronised clients.

That doesn't require unpredictability. For example, Mersenne Twister seeded from /dev/urandom would work fine for that, even though it's predictable because Mersenne Twister is predictable.

It does not require true unpredictability, the key aim being to have each host retry at a different time.
There is no need to cryptographic strength, which is costly, and pseudo-randomness is enough and much cheaper.

I think you're agreeing with me that unpredictability isn't necessary (e.g. Mersenne Twister would work fine).

I see you’ve replied to quite a few of the comments in this thread, but I think the basis of the disagreement isn’t in the specifics, but because you’re using a stronger definition of “unpredictability” than they are.

I believe I'm using the same definition of unpredictability as the website. If other people are using other definitions that is indeed going to cause a lot of confusion.

Today I learned that there are other aspects for CSPRNG beside the stronger definition of unpredictability. Wikipedia mentions inability to calculate previous values in case the hidden internal state gets revealed. So I assumed that top question was intentionally asking about weaker definition of predicatability not PRNG that have good enough unpredictability for CSPRNG but doesn't match other requirements.

Some would say Monte Carlo methods, but I'd disagree. If the results are reliant on your RNG method I would not settle for less than crypto strength (and methods like ChaCha20 can generate random data at 4GB+ per core per second on a modern CPU).
There is a time and place for non-CS rngs, and it is in randomized methods whos correctness/results does not rely on the RNG.

You're going to validate your results anyways, aren't you? Non-cryptographic random number generators are not guaranteed to introduce bias, a given implementation of a monte carlo simulation might introduce bias via a bug or a poorly chosen modeling. If you need to validate for bias anyways, so you might as well verify by checking against a cryptographic random number generator as well as whatever bias tests you may have at your disposal and then switch over for the speed.
A good non-cryptographic random number generator like xoshiro256 can generate at 4 times the speed of a chacha20 random number generator. Depending on how many models you need to compute and the desired precision of those models and how many random samples you need per model, this can easily be the difference between hours and days, or days and weeks.

This surprises me. With Monte Carlo methods, wouldn't you rather want quasi-random numbers[0], because they allow the simulation to converge asymptotically faster? Those are certainly not anything like crypto-strength.
[0]: https://en.wikipedia.org/wiki/Low-discrepancy_sequence

This is my understanding as well. In a classic MC problem, global illumination with path tracing, low discrepancy-based sampling converges about twice as fast as random numbers. The Cycles renderer in Blender doesn't even give you the option to use random numbers, just a choice of low discrepancy sequnces [1].
[1] "Pattern" section here: http://builder.openhmd.net/blender-hmd-viewport-temp/render/...

The suggested constants for additive recurrence in that wiki article have given me grief in the past. It is surprisingly simple to do extremely well with better choice of constants:
http://extremelearning.com.au/unreasonable-effectiveness-of-... (yes, no HTTPS, but incredibly illustrative)
Discussed in 2018: https://news.ycombinator.com/item?id=17873284

> methods like ChaCha20 can generate random data at 4GB+ per core per second on a modern CPU
For MC path tracing (graphics) this is at least an order of magnitude too slow.

Can you expand on this? I’d like to read more. Do you mean you’d like 40GB/core/second, or something else?

Well I mean you might need quite a number of random numbers per second, in this case 32bit floats was what we used.
Even fairly trivial scenes can require over 20 random floats per sample and more complex scenes over 100. And you want to actually use those random numbers for calculating reflections, intersections etc. In the renderer I worked on the PRNG typically took at most 10% of total CPU time.
So assuming the above those 4GB/s would translate into less than 5k samples/sec, which would be considered quite slow.
Just to refresh my memory I just ran a quick test with a fairly simple scene. There's 6 samples for the camera, at least 3 per path vertex up (depth 32) and another 2 per light (8 in this scene). There might be some more I'm forgetting but lets use that a lower bound. For this scene then that means 6 + 3 * 32 + 2 * 8 = 118 random numbers per sample. On a single core I got 14.04kS/s, so that works out to at least 1.6M random numbers per second.
And this renderer was focusing more on physics and fidelity rather than speed. For animations and similar you'd need a renderer that's at least an order of magnitude faster than the one I worked on.
For reading further you could try PBRT[1]. It's a great book but not free. Luckily enough though the free chapter is about sampling and reconstruction so you can get a feel from that what is needed.
[1]: https://pbrt.org/

This is a great answer and very helpful, thank you.

It is you that is off by several orders of magnitude. 4GB/sec is 10^9 random floats per sec, and using your 118 random numbers per sample that'd be 8.5 million samples/sec. In other words, it's not the RNG that's your bottleneck at all.

Well that was certainly embarrassing. On the other hand I overlooked that in my test scene it samples the lights at every vertex, and I forgot it had textures which needs at least 2 coordinates per vertex. So it needs at least 10 * 32 * 2 = 960 random values for that.
I also recall that we tried MT but found a quite noticeable impact on speed compared to what we had, and on the PGC performance page MT is listed in the tens of GB/s. Perhaps our implementation was considerably worse though, I can't recall us testing it alone like that.
As I mentioned though, that renderer was more about physics and fidelity. Typical render times for even a preview would be a minute, for final single-frame stills tens of hours to several days on a single computer was common.
For animations you don't have that kind of time, so you need a orders of magnitude more samples/sec.

>methods like ChaCha20 can generate random data at 4GB+ per core per second on a modern CPU
That's around 30x slower than a decent version of PCG, which also has a lot of variants to cover a lot of use cases.

> If the results are reliant on your RNG method I would not settle for less than crypto strength
Whenever a post on PRNGs comes up, I'm reminded of this post from a while back about Chrome:
https://medium.com/@betable/tifu-by-using-math-random-f1c308...
Near the end is a Monte Carlo estimate of Pi using 10^10 iterations:
Chrome 3.1418697000 0.0002770464 1301.903s Firefox 3.1416998084 0.0001071548 249.595s Safari 3.1416692728 0.0000766192 7172.207s
The first observation is that the error was significantly higher for Chrome. The second is that Safari, which apparently did use a CSPRNG, was an order of magnitude slower. If you let Firefox run that long, I imagine that it would have performed many more iterations, resulting in much lower error.

Yes and no. How do you ensure you don't hit a bad stream? I don't think there is any guarantee. For a very long stream, crypto is going to be good. For a not so long one, I am not so sure

Situations where there is no cryptographic issue in sight and random number generation is a bottleneck. Graphics and simulations in games, for example

Does that actually require unpredictability? Or is it just a defense in depth type thing where we believe we don't need it, but some unknown vulnerability/attack might make unpredictability beneficial?

The numbers used here are not for security they are just to make the scene look nice or to make the simulation more robust.

So I think we agree that unpredictability isn't necessary. The definition of unpredictability I'm using is the one on the website: where Mersenne Twister is easily predictable.

Looking at your and other comments there might be confusion about definition of unpredictability. Unpredictable for user which is pretty low bar or unpredictable using best known mathematical techniques and available hardware. Wouldn't the second category be more less CSPRNG? As for first category and examples given. Requires is a weird question. Strongly requires as in it's impossible to make any game or visual effect without it - no. But in case of some design choices you might want some amount of unpredictability. You might want player not to fully predict enemies next move, or you might want a certain graphical effect which varies some parameter randomly within some distribution. Using a very poor pseudorandom generator there might became visible once it gets used in large amounts for placing objects spatially in the form of streaks, shapes or other patterns that wouldn't appear if true random or better quality psrng was used.

I think I and andreareina are using the definition from the website. Yes, I think other people are using other definitions, which is causing confusion.
> Wouldn't the second category be more less CSPRNG?
The website says PCG is "Challenging" to predict and ChaCha20 is "Secure". So I think this means that PCG isn't a CSPRNG, but still is harder to predict than Mersenne Twister.
But is this useful at all? I don't know. This thread started by andreareina asking that exact question: "What applications require unpredictability where you wouldn't go full csprng?" People immediately then misunderstood the question because they misunderstood how the word unpredictability is being used.
A player not being able to mentally predict enemies and not seeing visible patterns sounds like it might fall more under the website's definition of "Statistical Quality".

Yes: http://extremelearning.com.au/unreasonable-effectiveness-of-...
Sibling comments are completely correct. Graphics simulations often require quasirandom sequences; the particular sequence is not important, but any correlations in the sequence will be visible in the output as artifacts, so we want a decorrelated sequence.
If this is not enough of a real-world example for you, then Monte Carlo methods also show up in weather modeling, financial planning, and election forecasting. In those predictive systems, there is extreme uncertainty and dependence on initial conditions, which we model with quasirandom sequences and seed numbers respectively. By running many simulations with different random sequences and then examining all of the results statistically, we can get good estimates of future behavior.
Edit: Oh, you're not in good faith. Okay, cool story. Best of luck with whatever imaginary idea of "unpredictability" you're trying to define, but you might want to return to actual maths at some point.

Quasirandom is unrelated to anything we're talking about. Quasirandom intentionally makes the output very different from random (avoiding clustering).
Every other thing in the PCG website and in this thread attempts to be similar to random (with varying degrees of success). No one here is trying to intentionally be different from random.
> Sibling comments are completely correct.
No sibling comment says anything about quasirandom. The sibiling comment mentioning graphics (by Karliss) actually sort of disagrees with you, and says that we want stuff to be as close to random as possible for graphics so that players don't see patterns. Of course there can be multiple types of graphics situations, some where quasirandom would be useful (the blog you linked), some where a real random approximation would be useful (Karliss's situation).

Ah, I see what you mean! I was unknowingly being sloppy with terms, thank you for pointing that out.

These algorithms are fantastic for microcontroller applications. You can even choose the multiplicative constant so that it fits in a Thumb-2 immediate and save yourself a constant pool reference, with no degradation in quality for the output (as measured by spectral tests).

Why is unpredictability useful there?

It's true that needing strict unpredictability, but not true cryptographic security, is rare in a microcontroller application. Though it can be nice to have.
What makes PCG attractive for microcontrollers is really that it's of known good quality, its implementation is very small and very simple, and it ends up generating efficient code for 32-bit processors (i.e., ARM Cortex-Ms). That is not, and can not ever be, true for something like a 128-bit shift register. PCG is great for just tossing in when I'm working on a platform that has no built-in library rand() function, or where it's busted, or whether I don't want to bother figure out if/how badly it's busted. (With how easy PCG is to use, that last one covers every embedded platform ever....)
PCG is not the best RNG out there: it's not the highest quality, it's not the fastest, it's not the least predictable, it's not the strongest theoretically. (It isn't the smallest, either, but it's quite small and the smaller RNGs I know of are either code-golfed, which doesn't count, or truly garbage.) But it is a nice equilibrium between all of those things. And did I mention it's simple? Simple is really, really nice to have :)

Anywhere you want reproducibility
- Statistics,
- Deep Learning,
- Monte-Carlo simulation (finance, reinforcement learning, game AI, raytracing).
- Fuzzing
- Load balancing
- Peer selection (if non adversarial, otherwise use a CSPRNG)
Also non-determinism of CSPRNG (and floating points) would a huge issue for debugging machine learning models:
- https://www.twosigma.com/insights/a-workaround-for-non-deter...
- https://github.com/tensorflow/tensorflow/issues/3103
- https://discuss.pytorch.org/t/deterministic-non-deterministi...
- https://github.com/tensorflow/tensorflow/issues/2732
- https://github.com/soumith/cudnn.torch/issues/270
- https://github.com/pytorch/pytorch/issues/2831

The output of a CS_P_RNG is by definition reproducible. And there’s really only a small number of applications where, say, ChaCha8 would be too slow.

According to https://rust-random.github.io/book/guide-rngs.html
Chacha8 has a throughput of 2GB/s and xoshiro256++ has a throughput of 8GB/s
For Monte-Carlo, the RNG is definitely the bottleneck. For load balancing of short tasks the RNG is the bottleneck.

On my thermally-limited laptop, aes-128-ctr runs at over 9 GB/s. If pure speed is the goal, then AES-NI is faster than the fastest PRNG. Seek to a deterministic point by advancing the counter. Choose random seed with a fresh key. What more could you want? ("portable speed!")
You can eek out another 10% or so if you dial it back to the recommendations of the "too much crypto" paper: 9x AES rounds (versus 10).
https://eprint.iacr.org/2019/1492

I don't think GP is questioning the need for a good but unsecure PRNG.
What is questionable is the "somewhat secure" argument. Either you don't want adversaries to predict your numbers and you should use a good CSPRNG, or you don't care and predictability is not a property that matters.
As for reproducibility, all PRNGs give a reproducible sequence if you know the internal state, including the secure ones. You have to mix in a source of entropy to make them non-deterministic. The predictability we are considering here is when the attacker doesn't have access to the internal state.

Conversely, why pay the massive speed penalty for a csprng when you do not need to?
I'd suspect the majority of random numbers generated in the world don't need crypto, they need speed. The world's supercomputers are not doing crpyto, they're doing simulations. Most people are not doing crypto most of the time - and when they're gaming in any manner, no need to pay csprng tax.
The only place one should use a csprng is for adversarial situations.
Use the right tool for the job, correct?

Being too easy to predict may break the blackbox nature of the PRNG (you might "predict" it by accident).
For example you can increase the quality of a RNG sequence r(n) by adding a multiplicative hash, r'(n) = A r(n) for some good constant A. A consumer treating r' as a blackbox expects B r'(n) = AB r(n) to be a good random sequence, but if B is close to the inverse of A, the constant AB may no longer be "good".

They describe rc4 as secure, which it hasn't been considered for years, so I'm not sure how seriously to take this site

Speaking of rc4, what are the reproducibility issues? Quick search on mobile didn't turn anything up. Is it just the "alleged" designation, i.e. no confirmation that it implements Rivest's original cipher?

IRRC The real RC4 was licensed to Novell and used in Notes.
People was later able to use the leaked, alleged rc4 algorithm to decrypt messages encrypted by Notes. That basically confirmed that the algorithms are the same.

"secure" in the website refers to predictability. Do you have a source on how to predict rc4?

The RC4 stream has biases. This means you have something like "bit X is slightly more likely to be 1 than 0". This isn't "predictability" in a sense that you know what it'll be, but it's bad enough for certain applications. How much it matters probably depends how exactly you design your RNG, but it seems like playing with fire and is easily avoidable by using a cipher without that property.

I believe numpy.random uses PCG by default. https://numpy.org/doc/stable/reference/random/index.html

I've used Pcg32 via https://docs.rs/rand_pcg and been quite happy. That being said I don't rely on excellent quality and haven't tested it. One of the main reasons I use it is that the implementation works perfectly in WebAssembly.
I use it to deal tiles in my version of online Azul: https://tiles.kevincox.ca
I also used it to simulate the Red7 game for strategy testing: https://gitlab.com/kevincox/red7-sim

Is there a fork of Fortune that uses the PCG, Xoshiro or wyhash algorithm?
I am not fluent in C or Rust and time constrained, otherwise I would have taken a shot at it
https://raw.githubusercontent.com/shlomif/fortune-mod/master... https://raw.githubusercontent.com/wapm-packages/fortune/mast...
Or better, with an entropy source like rdrand or rdseed?

Rdrand is not generally considered trustable, and the algorithm it uses is not known.
The main use for rdrand is to mix it with other entropy sources to produce a seed for another rng.

TinyCC example in README is wrong, should have trailing '-': as in "cat pcg_basic.c pcg32-demo.c | tcc -run -"

Here’s a Javascript implementation,
https://observablehq.com/@jrus/permuted-congruential-generat...
It’s a bit of a pain because Javascript can’t do native 64-bit integer arithmetic. But it should still be fast enough for most purposes.

Vigna's RNGs are faster and as good statistically so it's not clear why you'd use PCG.
They are a neat theoretical construction however I believe they have some serious flaws when attempting to split and construct multiple streams.
Honestly though RDRAND is cheap enough that I'd take true randomness over determinism.

And there are Haskell bindings: https://hackage.haskell.org/package/pcg-random
Nice!

One might be interested in https://github.com/wangyi-fudan/wyhash

Recently added to my dieharder: https://github.com/rurban/dieharder/blob/master/dieharder/wy...
but I still need to add more tests to get a better quality comparison against the xoshiro's

For "Arc4Random" it says "Reproducible Results: Not Always".
Can an algorithm really produce a non-reproducible result?

There are implementations of Arc4Random which introduce entropy during generation. So, it's not a design feature of the algorithm as much as it is an implementation detail.

https://www.pcg-random.org/other-rngs.html#arc4random explains what they meant:
> The BSD implementations (which are the only widely used ones) have several additional issues
> • No facility for a user-provided seed, preventing programs from getting reproducible results
> • Periodically “stirs” the generator using kernel-provided entropy; this code must be removed if reproducible results desired (and is removed from the C++ adaptation I created for testing purposes)

Thanks for the info. I wonder why the openssl implementation wasn't used:
https://stackoverflow.com/q/9329631/830749

Depends on what you're counting for determinism. Arc4Random uses the system entropy pool, so it's non-deterministic from a user perspective.
In a more direct sense, yes. If you're allowed to keep secrets (like internal state), it's possible to produce random numbers algorithmically for certain (weak) definitions of random, even with a deterministic machine. A simple example of this would be sequential bits of a normal number. As you strengthen your definition of randomness you pretty quickly get into non-computable territory though.

Sounds pretty undecidable to me to proof that a pseudo number generator has a challenging prediction difficulty.

The pcg-random methodology is very good. The basis is the following pattern:
#1: Have a "counter" of some kind. The simple counter trivially creates a maximum length cycle. "seed++" is one such counter.
#2: Have a "hash" that converts the counter into a random number, using a 1-to-1 bijection. There are a great many 1-to-1 bijections.
So your RNG is basically:
oldSeed = seed; seed = counterFunction(seed); return hash(oldSeed);
------------
I used this methodology to make a pretty fast generator myself. The coding was done in a weekend, but it took some weeks to test: https://github.com/dragontamer/AESRand
For AESRand:
"counterFunction" is a SIMD 2x64-bit Add over the XMM register. I chose an odd number arbitrarily (which are just the first 16 prime numbers: 0x01030507...), which will trivially cycle after 2^64 numbers.
"hash" is aesenc(aesenc(seed, constant), constant), where constant is an arbitrary (chosen to be the same odd number that was used in the "counterFunction" step). The 2nd parameter to aesend is just an XOR.
I also run a 2nd parallel aesdec(aesenc(seed, constant), constant) to generate a 2nd set of 128-bit random numbers, for 256-bits to be made across the hash. Yes, a 128-bit seed "hashes" into a 256-bit random number. Since this passes statistical tests, its probably fine, and this is a good source of instruction-level-parallelism.
All in all, I achieved 30GB/sec random numbers. Or 256-bits of random numbers every 3.7 cycles that passes BigCrush, TestU01, and PractRand.
--------
AES is a 1-to-1 bijection: that's a necessary condition for AES to be decoded. Though I use AES, this function is NOT cryptographically sound. I'm just using AES because its the fastest high-quality bijection in the entire modern CPU instruction set. x86, ARM, and POWER9 all implement single-cycle AES instructions.
It is possible to write a portable AESRand across the different CPUs (ARM, x86, and POWER9). I got far enough to prove that its possible, but then my real work started to ramp up and I had to drop this hobby project. Its very tricky to do so: ARM, x86, and POWER9 implement AESENC slightly differently: shuffling the fundamental steps in different ways.
Or in the case of POWER9, it executes in big-endian mode instead of little-endian (like ARM / x86). Redesigning the algorithm to be portable across the shuffled "SubBytes" and "MixColumns" steps between the CPUs is tricky but possible.

Would the outputs of these algorithms be considered pseudo-random?

The Drama between the author of PCG (u/ProfONeill) and the author of xoshiro (u/sebastianovigna) is one of the more entertanining parts of the C++ community. Too bad that despite that fierce competition, the <random> standard header itself is universally hated.

entertaining isn't really the word I'd use…

<random> and <chrono> have really been in a death match of "C++ standard libraries that are super-annoyingly C++", but they've both been absolutely destroyed by <range>, i think.

As in range being better or even worse? I haven't tried it out yet.

From what little I've used it, <range> is a C++ nightmare. Compile times explode and every time you get a tiny type error (which is impossible avoid, because the library is very persnickety about types) you get a bazillion pages of template errors.
Concepts and modules (supposedly) fix these issues, and I'm not going to use ranges again until those two are very mature features of C++. Even if you ignore this stuff, it's incredibly "C++ified" in just the worst way, with incredibly obtuse templates and type concepts all over the place.

I agree regarding <random>, but <chrono> is a work of art.

I like <chrono>. But I recently used the not quite yet standard "date" library. And that is super confusing in combination with <chrono>. You end up having an overlap of some functions and classes, some of which are in the date namespace, some of which are in chrono/std. And functions don't even properly error on compile when you do things wrong, but quietly misbehave. I hope this will solve itself once both arrive in compilers and both are in std:: namespace.

I don't know man, if I have to do another std::chrono::duration_cast, i might chuck my computer out of a window.

We’re so far off topic, but I agree with you SO much. <chrono> completely resists my attempts to remember how to do anything with it, no matter how many times I have needed to do something trivial like “time this region of code.”

This cppunk design aims to provide building blocks for you to build your own solution instead of some ready solution out of fear that they might misdesign something, that's why it's so heavily customizable. So yeah, you're supposed to roll a layer on top of it and build a component with reasonable functionality for this day or for your case.

I love <random>. Really. Sure, some other languages make the simple cases a little simpler, but no other system offers up the flexibility and control that <random> does.
Lets take PCG's author's comments one by one:
https://www.pcg-random.org/posts/cpp-seeding-surprises.html
Re: Predictability. I don't care. Truely. If unpredicatablity is important, the application must use a cryptographic random number generator. Those are the only known family that are hard-to-predict. Valuing un-predictabiltiy from a non-cryptographic PRNG has always been one of PCG's demerits in the xoshiro-versus-pcg debacle.
Re: Seed_seq's problems. The biases she's making out to be catastrophic are really quite small. In actual scientific monte carlo simulations, they don't affect things at all. I want to know the difference between 10^6 floats generated from the gaussian distribution, one with seed-seq's optimally seeded and one with it sub-optimally seeded. Because the "motivating scenario" isn't. You shouldn't ever be using a PRNG if all you need is one random number. You just grab a seed from a strongly-random generator like /dev/random.
The argument about seed_seq failing to be a bijection is completely irrelevant. You just need it to uniquely select one internal state of MT from the one initial value. So long each sequence of the first 600-someodd values drawn from it are unique, you've done that.
The demonstrated bias in MT's initial conditions doesn't matter one whit.

I think one of the main criticisms of <random> is that the distrubutions are implementation-defined. That means you get different outputs based on your compiler, even if your seed and even the rng itself is the same.

For better and for worse, this is a part of the standard where the committee deliberately under-specified things to allow room for improvement.

Reply on news.ycombinator.com