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.
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.
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.
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.
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 ?
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.
> 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]
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]
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.
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)
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.
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?
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.
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?
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.
I've always wondered, if you started recording audio, can you treat the least significant bit as random? Perhaps as an alternative to a real hardware random number generator?
I gotta think there are going to be some periodics in there that will be toggling the LSB. Like some hum from some device far away will be at the right tiny amplitude to toggle it in a predictable way. Also the ADC hardware could concievably get stuck.
The whole system breaks because someone didn't set up their pulseaudio correctly?
and what if you need 1TB of random data? With 48kHz audio you would be waiting 5000 years haha. 1MB is still more than a day
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!
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.
Please tell me if I'm off-base here, but something I always thought about and have been toying with is the notion that "there's no true random in this universe."
From a particle physics perspective, as an observer in the electromagnetic spectrum, we're always observing through a reference frame based on the speed of light in relation to the observed object. Because it's always in reference to a constant, c, anything perceived at random can theoretically be measured if you had the position of the observer at the time of observation, right?
Any fan of determinism would need to tackle quantum physics and what seems like unavoidable randomness in it (and there are such theories, but they offer little hope of getting around the randomness from our point of view, since they hide the order from us). The typical example of a random phenomena in nature is radioactive decay. You can't predict when any given nucleus will decay, only the probability that it will happen (which gives the half-life).
How so? I also find randomness profound but not sure what you mean but not belonging in the materialized world. Particle decay/Radiation is a pretty random process I believe?
Some confusion? I was saying "time is not material".
In my conception time is made out of events, and the events are I suppose all material, and all have probabilities. So maybe time follows inevitably from matter. But I think it exists in its own right as a phenomenon that isn't material. There are such things. Knowledge is another one.
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:
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.
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.
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.
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.
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.
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.
I took it as being a tongue-in-cheek way of saying "mathematicians."
> 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/
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]
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.
The default bit generator in NumPy is PCG-64 [1].
[1] https://numpy.org/doc/stable/reference/random/bit_generators...
> 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)
What does it mean to "break" PCG? It's not a secure random number generator.
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.
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.
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?
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.
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?
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.
From the title, I expected to see a list of recently-generated random numbers.
I got a 27 yesterday.
I've always wondered, if you started recording audio, can you treat the least significant bit as random? Perhaps as an alternative to a real hardware random number generator?
Yeah it would be fun to play with...
I gotta think there are going to be some periodics in there that will be toggling the LSB. Like some hum from some device far away will be at the right tiny amplitude to toggle it in a predictable way. Also the ADC hardware could concievably get stuck.
The whole system breaks because someone didn't set up their pulseaudio correctly?
and what if you need 1TB of random data? With 48kHz audio you would be waiting 5000 years haha. 1MB is still more than a day
> and what if you need 1TB of random data? With 48kHz audio you would be waiting 5000 years haha. 1MB is still more than a day
I think you dropped the "k" in "kHz" in your calculations.
If you are so inclined, you can build your own random number generator in hardware, which uses a Geiger counter: https://www.instructables.com/Arduino-True-Random-Number-Gen...
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!
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!
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.
https://www.pcg-random.org/posts/bounded-rands.html
i thought they were all built on the compression functions from secure hashes these days?
This is what I come to HN for.
I did not realize xorshift no longer as favored! Permuted Congruential Generators seems very cool. https://en.wikipedia.org/wiki/Permuted_congruential_generato...
Xorshift, LCM and hardware rdrand work just fine. PCG and Weyl are overkill.
sure, a += b is overkill
Hardware rdrand, lol! Totally broken
Please tell me if I'm off-base here, but something I always thought about and have been toying with is the notion that "there's no true random in this universe."
From a particle physics perspective, as an observer in the electromagnetic spectrum, we're always observing through a reference frame based on the speed of light in relation to the observed object. Because it's always in reference to a constant, c, anything perceived at random can theoretically be measured if you had the position of the observer at the time of observation, right?
Am I way off-base here?
Any fan of determinism would need to tackle quantum physics and what seems like unavoidable randomness in it (and there are such theories, but they offer little hope of getting around the randomness from our point of view, since they hide the order from us). The typical example of a random phenomena in nature is radioactive decay. You can't predict when any given nucleus will decay, only the probability that it will happen (which gives the half-life).
random numbers are not exactly random.
natural random numbers are not (exactly) random or artifical generated random numbers are not (exactly) random?
Randomness is far more profound than it appears to be. Probably it doesn't even belong to the real (materialized) world.
How so? I also find randomness profound but not sure what you mean but not belonging in the materialized world. Particle decay/Radiation is a pretty random process I believe?
Possibly connecting random events to time, which is not material.
The transformation of a particle into two more basic particles is absolutely material.
Some confusion? I was saying "time is not material".
In my conception time is made out of events, and the events are I suppose all material, and all have probabilities. So maybe time follows inevitably from matter. But I think it exists in its own right as a phenomenon that isn't material. There are such things. Knowledge is another one.
Noether's Theorem states that it is fundamental to our real world - or else the apparent, fundamental symmetries of our physics are wrong.
I dunno ... his saucy language made this very difficult to read.