A brief history of random numbers (2018)

Posted by todsacerdoti 10/28/2025

A brief history of random numbers (2018)(crates.io)

214 points | 72 comments

camel-cdr 10/28/2025|

A history about random number generation isn't complete without mentioning George Marsaglias work.

He is responsible for multiply-with-carry, xorshift (the original version), KISS (a high quality generator predating the mersene twister) , the Ziggurat algorithm, diehard

Fun fact, one of the earliest methods for generating random mumbers, the middle square method, actually still passes all moderm statistical randomness test suites, if you hook up a weyl sequence to it: https://arxiv.org/abs/1704.00358

This, the middle square weyl sequence PRNG is my favoeite PRNG, because it's simple enough to implement from memory:

    uint64_t x, weyl;
    uint32_t msws(void) {
        x = x * x + (weyl += CONSTANT);
        return x = (x >> 32) | (x << 32);
    }

You just take a number, square it, advace and add the weyl sequence to it amd finally swap the lower and upper bits, using the trucated result as the output.

The CONSTANT is pretty much arbitrary, it just needs to be odd and not too regular. A good rule of thumb is to have no repeating or zero nibbles in each group of 4 bytes, e.g. 0xB5AD4ECEDA1CE2A9.

avadodin 10/28/2025||

That paper doesn't mention how many rounds it passed on the statistical tests, just that they tested 25000 seeds. They also don't definitely state a period but 2^64 with 192 or 384 bits of state is not that impressive. Furthermore, your version here uses only 128 bits so it is not clear to me that it is equivalent to the ones presented in the paper.

camel-cdr 10/28/2025||

msws32() from the paper is the exact code I wrote above. The "s = 0xb5ad4eceda1ce2a9" is not part of the state, it's the CONSTANT.

I've tested msws32 it passes TestU01s BigCrush and didn't fail in >=1 TB of PractRand (I stopped after that). A scaled down msws16 fails PractRand after 2 GB, a msws24() variant passes >=256 GB (I stopped after that).

It's certainly not as good as more state of the art PRNGs like PCG, xoshiro, romu, sfc64, tylo64, but it is very simple and has quite high quality output, much better than any similarly simple to construct PRNG I know of.

avadodin 10/28/2025||

Sorry for misrepresenting it a bit.

The renaming and the having the constant be a variable confused me when skimming for the parts that I was looking for.

So, the state is 128 or 256 for the versions presented and 64 for msws16.

I don't remember if running PractRand in word mode changes the way it reports results but either way failing at 2GB would mean it failed even before going through the whole Weyl sequence although the period itself isn't necessarily reduced.

I'm not sure if the middle-square is acting as a decent non-linear scrambler on the poor adder state or if both combined manage to hold 30 bits worth of state. Swapping the adder with an lcg or lfsr on msws16 would provide an answer.

PractRand has the benefit that we can look at where and how failure happens in these reduced versions so I think the criticism ultimately stands regarding the paper.

LPisGood 10/28/2025||

The Ziggurat algorithm is very important and widely used. There are some side channel vulnerabilities in differential privacy applications based on the details of this algorithm.

ot 10/28/2025||

> Since nobody had figured out any downsides to PCG's yet, everyone shrugged and said "might as well just go with that then", and that is where, as of 2019, the art currently stands. The problem is solved, and life is good.

I wonder who "everyone" was, I'm not aware of many high-profile projects adopting PCG as a default. As of 2025, several high-profile runtimes (including all the major browsers) use xorshift variants [1]

Is there a list of users of PCG?

[1] See Adoption section in https://prng.di.unimi.it/

vlovich123 10/28/2025||

It kind of doesn’t matter if there are users - there are people still stupidly using Mersenne Twister. The point is that PCG is better than xorshift and related in that family. That other high profile applications haven’t switched is besides the point that PCG is objectively better:

> O'Neill proposes testing PRNGs by applying statistical tests to their reduced-size variants and determining the minimum number of internal state bits required to pass.[7] TestU01's BigCrush examines enough data to detect a period of 235, so even an ideal generator requires 36 bits of state to pass it. Some very poor generators can pass if given a large enough state;[8] passing despite a small state is a measure of an algorithm's quality, and shows how large a safety margin exists between that lower limit and the state size used in practical applications. PCG-RXS-M-XS (with 32-bit output) passes BigCrush with 36 bits of state (the minimum possible), PCG-XSH-RR (pcg32() above) requires 39, and PCG-XSH-RS (pcg32_fast() above) requires 49 bits of state. For comparison, xorshift*, one of the best of the alternatives, requires 40 bits of state,[5]: 19 and Mersenne twister fails despite 19937 bits of state.[9]

ot 11/1/2025|||

> It kind of doesn’t matter if there are users [...] The point is that PCG is better

No that's not the point that the article makes and that I'm questioning, it says "everyone shrugged" which implies consensus, and I'm asking for evidence of that consensus, not of the objective quality of the two generators.

Also I don't think that that paragraph is even close to demonstrating "objectively better": the author of PCG pointed out one arbitrary metric, minimum state size, where PCG beats old variants of xorshift* on a statistical test suite, and in the meantime much better variants have come out. That metric is meaningless since everyone uses much bigger state anyway.

RNGs are a tricky subject, there isn't a singular measure of quality, statistical tests are necessary but not sufficient. The best testament to RNG quality is wide adoption, which builds confidence that there aren't undiscovered failure modes.

camel-cdr 11/2/2025||

Agreed, you can get minimum state size by just using a linear counter and a sufficiently good hash function.

The metric is quite useless, what matters way more IMO is the quality of scaled down variants.

adgjlsfhk1 10/28/2025|||

IMO there's plenty of reason to use Xoshiro over PCG. the quality differences between the best xoshiro and pcg differences are minimal (especially because most languages use a 256 bit state since it makes it easier to split/jump without worrying about duplicate streams), and Xoshiro generators tend to be easier to SIMD for when you need lots of random numbers.

vlovich123 10/28/2025||

There are SIMD versions of PCG and most variants you find online aren’t SIMD.

WarrenWeckesser 10/28/2025|||

The default bit generator in NumPy is PCG-64 [1].

[1] https://numpy.org/doc/stable/reference/random/bit_generators...

aj_hackman 10/28/2025|||

Much like my beloved comb sort, I use xorshift because the implementation is small and it's Good Enough. God's Own 100 SLOC PRNG would have to be near-perfect and take three clock cycles to contemplate switching.

camel-cdr 10/28/2025||

> nobody had figured out any downsides to PCG's yet

BTW, people have broken PCG already: https://hal.science/hal-02700791/file/main.pdf

It takes up to 20000 CPU hours to break the seed from 512 output bits with an unknown state, increment and multiplier. (the multiplier is usually fixed constant)

tptacek 10/28/2025|||

What does it mean to "break" PCG? It's not a secure random number generator.

camel-cdr 10/28/2025|||

Seed recovery. It's not meant to be cryptographically secure, but previously nobody had reversed it.

Showing that reversal takes that many CPU hours shows how good the PRNG quality is.

mahemm 10/28/2025|||

To me this is completely unrelated to the quality of the PRNG, because security is explicitly a non-goal of the design. A general-purpose non-cryptographically secure PRNG is evaluated primarily on speed and uniformity of output. Any other qualities can certainly be interesting, but they're orthogonal to (how I would evaluate) quality.

tptacek 10/28/2025||

Right: put differently, why would you bother to select among the insecure RNGs an RNG whose "seed" was "harder" to recover? What beneficial property would that provide your system?

avadodin 10/28/2025||

CSPRNGs have all of the desirable properties for the output.

All else being equal, I don't think it is possible for a trivially reversible generator to have better statistical properties than a generator whose output behaves more like a CSPRNG.

It can definitely be good enough and or faster, though.

tptacek 10/28/2025||

Right, I think defaulting to a CSPRNG is a pretty sane decision, and you'd know if you had need of a non-CSPRNG RNG. But what does that say about the choice between PCG and xorshiro?

avadodin 10/29/2025|||

Defaulting to a CSPRNG pre-seeded with system randomness is not a bad choice per se(especially given many users don't know they need one) but current ones are much slower than the RNGs we are discussing.

If you're going to provide a non-CS one for general simulation purposes, you probably want the one that is the closest to indistinguishable from random data as you can without compromising performance, though.

Some people will have more than enough with a traditional LCG(MC isn't even using RNGs anymore) but others may be using more of the output in semantically relevant ways where it won't work.

If Xoshiro's state can be trivially recovered from a short span of the output, there is a local bias right there that PractRand lets through but that your application could accidentally uncover.

The choice is: Are the performance gains enough to justify that risk?

tptacek 10/29/2025||

Why does it matter if the state can be trivially recovered? What does that have to do with the applications in which these generators are actually used? If the word "risk" applies to your situation, you can't use either xorshiro or PCG.

avadodin 10/29/2025|||

This is too deep to reply but if a bit is dependent on the value of a bit a couple bytes back then it is not acting randomly.

It's not about security.

I hope you can agree that if every time there is a treasure chest to the left of a door, a pink rabbit spawns on the top left of the room, that's not acting very random-like.

I'm not taking a position on the perceived added value of PCG over Xoshiro.

mahemm 10/29/2025||

The property you're talking about (next bit unpredictability) is important for a CSPRNG, but it doesn't matter at all for a PRNG. A PRNG just needs to be fast and have a uniform output. LCGs, for instance, do not have next bit unpredictability and are a perfectly fine class of PRNG.

avadodin 10/29/2025||

The paper that triggered this thread "breaking" PCG sees it as potentially in the same class of issues as using RANDU.

> our results […] do mean that [PCG']s output has detectable properties. Whether these properties may affect the result of Monte-Carlo numerical simulations is another matter entirely.

Again this is on PCG which required a breaking effort.

The short version of Xorshift as originally presented by Marsaglia outputting its whole state for example is bound to have behaviors like my room-generation example emerging fairly easily. Particularly, with low hamming-weight states.

I doubt Xoshiro's output is that bad but if presented as trivial to recover vs PCG, that to me indicates potential issues when using the output for simulation.

charlieyu1 10/28/2025|||

Any recoverability sounds very bad.

Why shouldn’t I just use eg sha512 on the previous hash and drop half the bits?

throwaway150 10/28/2025|||

> Any recoverability sounds very bad.

PRNGs are not meant to be cryptographically secure. If you don't want recoverability by all means use SHA512 or a proper CSPRNG.

But saying PRNGs are bad because there is recoverability is like saying salt is bad because it isn't sweet. PRNGs are not meant for non-recoverability and salt isn't meant to be sweet.

tptacek 10/28/2025|||

It's not bad because "preventing seed recovery" isn't the job of an insecure RNG. If you care about seed recovery, you must use a secure generator. There aren't degrees of security here; PCG is insecure, and (say) the LRNG or CTR-DRBG are not.

whyever 10/29/2025|||

I agree, but https://www.pcg-random.org/ still advertizes PCG as "challenging" to predict, and critizises other RNGs as predictable and insecure.

tptacek 10/29/2025|||

Right, that's a problem, because nobody that cares about this should be using PCG.

avadodin 10/30/2025|||

> Predictable — after 624 outputs, we can completely predict its output.

> we recovers[sic] all the secret information using 512 consecutive output bytes

oof

WalterGillman 10/29/2025|||

I wonder how much it would take to break mine.

https://github.com/waltergillman/xorshift_sbox

I have not been blessed by an education so I can't be eloquent and write proofs and papers and stuff but it passes PractRand for 4GB with only 32 bits of state.

Not very fast on modern computers, I will concede.

jkhall81 10/28/2025||

I thought this was a proper article. It was a good read. Then I start looking around at the page and was like 'where the hell am I? This is a rust crate readme?!'

derbOac 10/28/2025||

Is there a good text on random number generation that someone on HN can recommend? I've read about various generators, pseudorandom and truly random, but those have always been scattered across various places, and I'm wondering if there's a good solid unified text on all of them, in terms of families of them and their underlying ideas, and their advantages and disadvantages.

slybot 10/28/2025|

https://www.pcg-random.org/posts/bounded-rands.html

PantaloonFlames 10/28/2025||

This was entertaining and informative, the best kind of info. But one puzzle remains - why did the author keep mentioning slide rules as a tool that would reveal the non-randomness of some number series ?

I don’t get that part.

ChrisSD 10/28/2025||

They're using slide rule users as a stand-in for serious mathematician as opposed to people who incidentally use mathematics. It makes some sense in historical context but becomes a bit anachronistic after the invention of electronic calculators.

ordu 10/29/2025|||

Slide-rule is a sort of "trope". If you need to signal to readers or your book or watchers of your movie that some character has STEM education, you give them a slide-rule. There are other ways to do this, you can make them wear white coats. White coat is more popular though, if the author used white coats, I'm sure you'd be able to get it.

dcminter 10/28/2025||

I took it as being a tongue-in-cheek way of saying "mathematicians."

olivia-banks 10/28/2025||

I love how this is written. A lot of things nowadays on this site, if only vaguely, make me think it was written in part by an LLM, but this didn’t fall into that category. Great read, bravo!

glonq 10/28/2025||

From the title, I expected to see a list of recently-generated random numbers.

I got a 27 yesterday.

oniony 10/29/2025||

I just get 4 every single time.

dollylambda 10/28/2025||

Talk about skipping a `1.0` release. Is anyone else scratching their heads about this? Here https://hg.sr.ht/~icefox/oorandom/rev/46ca789e6bb68cfc5d838f... the project jumps from a 0.1.0 release to 9.3.0.

dollylambda 10/29/2025|

"The version number is inversely proportional to the likelihood that I will ever come back and do something that would require incrementing it."

LOL

dswalter 10/28/2025||

Refreshing when technical writing has a sense of style.

Read it and gain a gnawing sense of unease at how "good" things might really be at present!

lucasfcosta 10/28/2025|

This is what I come to HN for.

More comments...