Xorshift Generators
alanzucconi.com
alanzucconi.com
There is an undocumented xorshift implementation in tst.c.
There is no real use case for better non-CS generators, as explained by adrian_b back in 2021 [3].
[1] https://en.wikipedia.org/wiki/RANDU [2] https://arxiv.org/abs/1908.10020 [3] https://news.ycombinator.com/item?id=28886698
As someone who has spent considerable time working in these areas, I still appreciate advances.
Have you skimmed the linked thread?
> especially simulation/sampling approaches that are bound by the number and quality of uniform variates per second
Sorry, nobody does stochastic simulations where the number of uniform random numbers obtained per second is any sort of bottleneck. If you've spent considerable time on stochastic simulation, you already know this.
But even if you insist that you alone are doing some very weird stochastic simulation which is somehow bottlenecked on sourcing random numbers fast enough, the falling in planes phenomenon linked above would make xorshift-type generators a poor choice for most sorts of simulations. It introduces spatial correlations into any sort of lattice dynamics simulation (Ising model, percolation) and every high dimensional Monte Carlo integration. Beyond falling in the planes, since xorshift is linear over GF(2), it is also a particularly bad choice for nondeterministic cellular automata and Boolean dynamical systems which use parity, bit masks, or xors.
AES-CTR throughput on a modern CPU is higher than that of xoshiro256++, and much higher quality. No advances in non-CS PRNGs can beat that while maintaining the same quality. If your stochastic simulation is bottlenecked on random bits, CSPRNGs are still the way to go, and they don't interact in nasty ways with any dynamical system you can actually sinulate quickly.
I do a lot of testing and designing of things like hash tables and filters, and having a really fast, non-CS generator is incredibly useful for being able to clearly identify performance bottlenecks in designs. PCG has been spectacularly useful for that purpose for me.
As in, you were using state of the art generator X, and you couldn't see the performance bottleneck, but updating to a newer (faster, or same speed but higher quality) generator Y, and could subsequently identify the performance bottleneck?
If you're using PCG, not in the last 12 years.
(In a parallel comment I suggest trying AES-CTR for this use case)
While not a bottleneck as such, I contributed to a photorealistic path tracer using the Metropolis algorithm[1], and we got a 10-15% increase in samples/second when we switched from a decent to a much faster and better PRNG. Like you we didn't think the performance of it mattered much until we profiled it.
Granted this was a decade or so ago, would be interesting to compare the state of the art PRNGs.
Anyway, just pointing out that there can be real-world cases.
[1]: https://en.wikipedia.org/wiki/Metropolis_light_transport
Actually, I spent a considerable amount of time in my doctorate and postdoc doing this.
Any kind of MCMC sampling of a simple model tends to be bound by the rate you can draw variates.
Examples of this include: Gillespie simulations of chemical kinetics, Ising and Potts lattice models (including their roughly bazillion variations), and anything resembling bootstrap or permutation sampling.
Just because your problems aren’t bound by the rate of drawing uniform variates doesn’t mean that these problems don’t exist. It just means that you have a narrow view.
Almost everyone should use a csprng, but iykyk.
cpu: AMD Ryzen 5 5600X 6-Core Processor
BenchmarkAES_CBC-12 100000000 10.96 ns/op
BenchmarkAES_CTR-12 83161234 14.36 ns/op
BenchmarkPCG-12 345336063 3.463 ns/op
BenchmarkChaCha8-12 174143492 6.894 ns/op
BenchmarkXoshiro256p-12 254343658 4.717 ns/op
BenchmarkXoshiro256pp-12 266837442 4.496 ns/op
cpu: Apple M4 Pro
BenchmarkAES_CBC-14 162698020 7.370 ns/op
BenchmarkAES_CTR-14 242501074 4.954 ns/op
BenchmarkPCG-14 197000988 6.083 ns/op
BenchmarkChaCha8-14 237430095 5.050 ns/op
BenchmarkXoshiro256p-14 252911710 4.738 ns/op
BenchmarkXoshiro256pp-14 252656401 4.745 ns/op
And using Golang? That ludicrously slow also.
To tell us what a cpu can do, do them using SIMD, you get pipelining and then many values per clock. Now try that with AES. Oh, you cannot, it’s not supported.
And people needing lots at full speed will do them on GPUs.
There is no world where even HW accelerated crypto comes close to non cs prngs on mainstream HPC systems.
I’ve a PhD, have written papers on PRNGs, have worked in both cs prng and high perf prngs, have done decades of HPC projects, scientific sims. I get called in to develop precisely these high performance systems, and when you want to replace trillions to quadrillions of PRNG calls with one costing 10-1000x more, you’d get deservedly fired immediately.
You keep arguing about AES style code on a CPU. That’s not where people do high performance code. Try implementing AES and a fast prng on a GPU. You’ll soon find out how absolutely terrible cs-prngs are at performance. The measuremt isn’t how many ns per prng. It becomes how many thousands of prng generated per ns.
It’s bafflingly shortsighted for people with zero work in this area to continue to argue this. Choose the right tool for the job. Don’t project ignorance as knowledge. Both are useful advice.
If Intel, AMD and Apple add a xoroshiro or PCG instruction and it produces pseudorandom numbers significantly faster than accelerated AES on those architectures, how does that affect your argument?
On the other hand, most simulations have moved on from random numbers to non-random space-filling sequences so the only non-CSPRNG application would be rolling fair dice for games and even there there is an argument to be made for CSPRNGs. So, perhaps I agree with you on the bottom line.
But I agree that if you're building something new aimed for modern devices, Marsaglia's xorshift128 wouldn't be my first choice! But I'd definitely want it in my RNG library for backward compatibility!
On Z80 it was only about as fast as RC4 which is also a good option in terms of performance and quality but whereas RC4 has a huge state, this one only has a 32bit state, the rest staying in ROM.
Yes there is. Not every system has the need or the resources to maintain a secure random sequence. You may also want a reproducible pseudo-random sequence in generative code that logs the seeds. Because of the misguided attitude that nobody needs these features, everyone who does need them has to roll their own now.
I'm sure there's something, but that category has to be shrinking every year. What does such a system look like this decade, that needs random numbers but can't easily implement something like AES?
> You may also want a reproducible pseudo-random sequence in generative code that logs the seeds. Because of the misguided attitude that nobody needs these features, everyone who does need them has to roll their own now.
I don't know what difficulty you're referring to. Basically every CSPRNG can be seeded easily and you can log the seed.