Better, cheaper, more abundant random numbers(economist.com)
economist.com
Better, cheaper, more abundant random numbers
https://www.economist.com/science-and-technology/how-to-generate-better-cheaper-more-abundant-random-numbers/21806558
42 comments
Quoting von Neumann about software rngs is ignoring most of a century of development in the field. There are a plethora of high quality CPRNGs that are almost certainly totally unbreakable if you mix in a few bits of hardware randomness per megabyte of random numbers.
Also this was in a paper where he was working on a PRNG, and later he says "If the [pseudorandomly generated] digits work well on one problem, they seem usually to be successful with others of the same type." So this is more of a "Yeah this is technically wrong but I did it and it worked" sort of thing.
[deleted]
Is there some reason why you can’t use an arbitrary cryptographic hashing algorithm on “secret app id + counter” repeatedly?
Other than having to keep the secret app id actually secret.
Other than having to keep the secret app id actually secret.
PRNGs and CPUs are stupidly fast these days. I'm not really convinced that the problem is abundancy of pseudo-random bits, not at least for simulations. A well written PRNG should execute at the same speed as a memset in fact (at least, for the creation of PRNG-bits before processing)
Massaging the bits into proper form: using modulus operator, requires like 80-cycles (aka: a division) on 5-year old CPUs and maybe 20-cycles on a very modern core (with the past 3 years, as Intel seems to have put a lot of work optimizing division). So the bulk of the time is on this massaging process actually.
--------
Even if the bulk of the CPU time is spent converting the uniformly random bits into usable integers (division / modulus is really slow!!), or usable floats / normal distributions or whatever... I still expect the typical core to handle 100-million pseudo random numbers per second... __per core__.
Seeding your PRNG with a true random seed every now and then will ensure large-scale randomness.
I think cryptographers might need something higher quality, but key-generation is quite uncommon, so you wouldn't need to be doing millions-and-millions of keygens per second, would you?
Simultaions need lots of random numbers, but those random numbers don't need to have entropy guarantees, but instead have weirder requirements (not only speed of generation, but also the ability to rerun your simulation... you actually want deterministic random-number-generators for simulations to verify your results). So in these cases, PRNGs are not only needed, but superior to a true RNG.
There's also the weird case of quasi-random, a term I learned from the graphics community. You want your rays to be random-ish, but actually "more uniform" than actually random. Its a more pleasant randomish pattern to look at, leading to pleasant and artistic images (https://en.wikipedia.org/wiki/Halton_sequence). Quasi-random raytracing is a so called "Biased" generator, because the physical light models are probably closer to true random. However, quasi-random sequences lead to far less noise in far less time / samples, so they're more useful in practice.
--------
Ultimately, our x86 CPUs today have "true" RNGs built into the RDSEED instruction, pulling entropy from some kind of physical circuit that's highly sensitive to temperature conditions (thermal quantum noise generators inside of circuits. After all, heat is quantumly random as your electrons jump between states in the very small scale).
Massaging the bits into proper form: using modulus operator, requires like 80-cycles (aka: a division) on 5-year old CPUs and maybe 20-cycles on a very modern core (with the past 3 years, as Intel seems to have put a lot of work optimizing division). So the bulk of the time is on this massaging process actually.
--------
Even if the bulk of the CPU time is spent converting the uniformly random bits into usable integers (division / modulus is really slow!!), or usable floats / normal distributions or whatever... I still expect the typical core to handle 100-million pseudo random numbers per second... __per core__.
Seeding your PRNG with a true random seed every now and then will ensure large-scale randomness.
I think cryptographers might need something higher quality, but key-generation is quite uncommon, so you wouldn't need to be doing millions-and-millions of keygens per second, would you?
Simultaions need lots of random numbers, but those random numbers don't need to have entropy guarantees, but instead have weirder requirements (not only speed of generation, but also the ability to rerun your simulation... you actually want deterministic random-number-generators for simulations to verify your results). So in these cases, PRNGs are not only needed, but superior to a true RNG.
There's also the weird case of quasi-random, a term I learned from the graphics community. You want your rays to be random-ish, but actually "more uniform" than actually random. Its a more pleasant randomish pattern to look at, leading to pleasant and artistic images (https://en.wikipedia.org/wiki/Halton_sequence). Quasi-random raytracing is a so called "Biased" generator, because the physical light models are probably closer to true random. However, quasi-random sequences lead to far less noise in far less time / samples, so they're more useful in practice.
--------
Ultimately, our x86 CPUs today have "true" RNGs built into the RDSEED instruction, pulling entropy from some kind of physical circuit that's highly sensitive to temperature conditions (thermal quantum noise generators inside of circuits. After all, heat is quantumly random as your electrons jump between states in the very small scale).
> Massaging the bits into proper form: using modulus operator, requires like 80-cycles (aka: a division)
It's not uncommon to instead treat the RNG data as a floating point number between 0 and 1 and multiply it by the modulus (adding or subtracting 1 as appropriate depending on whether you want, say, 0-20 or 1-20 as the output). So that's a float multiplication, an addition, and a conversion to integer. Still probably cheaper than 80 cycles.
But we're also burning 32bits of data to get 4.4 bits of output. When randomness was more expensive than CPU cycles they would throw a Linear Congruence Generator on top, which is a function can transform an input and achieve similar levels of entropy in the output. It might take 5 bits or 8 bits of data instead of 32, at least quadrupling the utility of your source. But that's mostly for historical purposes. As you say, the ratio of CPU to random decisions has shifted many orders of magnitude in the last 20 years.
It's not uncommon to instead treat the RNG data as a floating point number between 0 and 1 and multiply it by the modulus (adding or subtracting 1 as appropriate depending on whether you want, say, 0-20 or 1-20 as the output). So that's a float multiplication, an addition, and a conversion to integer. Still probably cheaper than 80 cycles.
But we're also burning 32bits of data to get 4.4 bits of output. When randomness was more expensive than CPU cycles they would throw a Linear Congruence Generator on top, which is a function can transform an input and achieve similar levels of entropy in the output. It might take 5 bits or 8 bits of data instead of 32, at least quadrupling the utility of your source. But that's mostly for historical purposes. As you say, the ratio of CPU to random decisions has shifted many orders of magnitude in the last 20 years.
Daniel Lemire has an excellent blogpost + paper of this technique you describe, except using the 64-bit multiplier circuit of CPUs.
https://lemire.me/blog/2019/06/06/nearly-divisionless-random...
The 64x64 bit multiplier outputs a 128-bit output in ARM and x86. You see the 64-bit number as a fixed-point integer between 0 and 1 (that is to say: 0xFFFFFFFF as a 32-bit number is .9999999...). Multiply by the 64-bit version, bit-shift the result down and bam, you've got a high-speed, low-bias result.
-----
So you can see the 64-bit number is a number between 0 and .999999...., that number is multiplied with "6" or whatever you care about (assuming you want to make a dice roll from 0 to 5), and the results are in the top 64-bits of the 128-bit number the multiplier circuit created.
Getting you slightly less bias, and losing the unnecessary int->float and float->int conversion.
-----
A bit of the cutting edge, but I gave it a few experiments and it clearly worked. I was working on an SIMD-version of this technique a couple of years back and it definitely works.
You can also SIMD-ify the integer->float conversion with some smart AND / OR instructions. (See the "toFloats" routine here: https://github.com/dragontamer/AESRand/blob/master/AESRand_P...)
Oh right, and you can also use the AES circuits to make random numbers, but that actually was really difficult for me to figure out just right (!!!). AES round function is surprisingly bad at shuffling bits around, but with enough effort I got something working (passes 8TB+ of PractRand tests and other statistical tests)
https://lemire.me/blog/2019/06/06/nearly-divisionless-random...
The 64x64 bit multiplier outputs a 128-bit output in ARM and x86. You see the 64-bit number as a fixed-point integer between 0 and 1 (that is to say: 0xFFFFFFFF as a 32-bit number is .9999999...). Multiply by the 64-bit version, bit-shift the result down and bam, you've got a high-speed, low-bias result.
-----
So you can see the 64-bit number is a number between 0 and .999999...., that number is multiplied with "6" or whatever you care about (assuming you want to make a dice roll from 0 to 5), and the results are in the top 64-bits of the 128-bit number the multiplier circuit created.
Getting you slightly less bias, and losing the unnecessary int->float and float->int conversion.
-----
A bit of the cutting edge, but I gave it a few experiments and it clearly worked. I was working on an SIMD-version of this technique a couple of years back and it definitely works.
You can also SIMD-ify the integer->float conversion with some smart AND / OR instructions. (See the "toFloats" routine here: https://github.com/dragontamer/AESRand/blob/master/AESRand_P...)
Oh right, and you can also use the AES circuits to make random numbers, but that actually was really difficult for me to figure out just right (!!!). AES round function is surprisingly bad at shuffling bits around, but with enough effort I got something working (passes 8TB+ of PractRand tests and other statistical tests)
Dice rolls rock
I'd say the real issue here is the quality of the article. It failed to adequately define the problem being solved by this group. I'd expect better from the Economist.
> Finding random phenomena in nature that can be transformed into computer bits is not easy...Otherwise, specialist, expensive hardware needs to be used to do things such as measuring heat flux through a silicon chip.
What happened to the good old days of taking a picture of a lava lamp and using that as your random number until you take another picture?
What happened to the good old days of taking a picture of a lava lamp and using that as your random number until you take another picture?
That sounds pretty big and expensive.
It is referencing this bit at Cloudflare: https://www.youtube.com/watch?v=1cUUfMeOijg
Actually I'd never seen that before. Using lava lamps to generate randomness predates Cloudflare by a few decades. :)
And Cloudflare's lava lamps are an homage to SGI's 1996 Lavarand:
https://en.wikipedia.org/wiki/Lavarand
https://en.wikipedia.org/wiki/Lavarand
A lava lamp is $25 and a really nice webcam is like $60.
Tangentially related, I had a fun time hooking the audio jack of my Geiger counter up to a digital input pin of an esp8266 the other day to generate random numbers from radioactive decay [1]. Not the fastest way to make random numbers. But fun nonetheless.
[1] https://partofthething.com/thoughts/making-true-random-numbe...
[1] https://partofthething.com/thoughts/making-true-random-numbe...
I own several electron tunneling based RNGs. I will say they are not all the same, there are differences in security, and other esoteric things that HN will probably downvote me for for lack of being in the know.
I will say that random numbers as a service is a viable business opportunity. And I have heard that micro QRNG chips are being put into new phones.
I'm a bit of an rng nerd
I will say that random numbers as a service is a viable business opportunity. And I have heard that micro QRNG chips are being put into new phones.
I'm a bit of an rng nerd
>I will say that random numbers as a service is a viable business opportunity
How do you compete with the free CSPRNGs provided by the operating system?
How do you compete with the free CSPRNGs provided by the operating system?
And how do you convince the customer that you are not cutting corners?
Just tell the customer they have to XOR bits from all randomness providers, and they're fine if at least one is truly random. This really sounds like a business where all competitors could hang out together!
Disclaimer: not a cryptographer. This is not cryptography advice.
Edit: cryptography
Disclaimer: not a cryptographer. This is not cryptography advice.
Edit: cryptography
Coinflips sounds pseudorandom.
Greying or mixing or whatever of pseudorandom or actual "trng" like static or radiation discharges is pretty well known. I.e. take some source of randomness for 10000 bits, xor with each other, and use that to seed a cryptographically secure generator, topping up the seed as more bits become available, is pretty much the gold standard for "I need 50gbit bitstream of 'random'"
The other part seems to be the binning/bucketing/curve fitting, or "massaging" the output of that to only gives numbers in the range under scrutiny, which sounds like an implementation detail to me, rather than something that you can configure at ... Runtime? Compile time?
I'm sure there are real HRNG (or sensors for TRNG) that can approach ludicrous bitrates, I've never had the luxury of one, and I'm not entirely sure I could be convinced the output was any "better" than a vetted arrangement from my second paragraph.
All of this is to say: okay but we already do that and massaging randomness to give us results we want is what all this modeling stuff ... is, so other than some off in the weeds magnetic film manipulation, I'm assuming that's modelled, too. It's just models all the way down?
Greying or mixing or whatever of pseudorandom or actual "trng" like static or radiation discharges is pretty well known. I.e. take some source of randomness for 10000 bits, xor with each other, and use that to seed a cryptographically secure generator, topping up the seed as more bits become available, is pretty much the gold standard for "I need 50gbit bitstream of 'random'"
The other part seems to be the binning/bucketing/curve fitting, or "massaging" the output of that to only gives numbers in the range under scrutiny, which sounds like an implementation detail to me, rather than something that you can configure at ... Runtime? Compile time?
I'm sure there are real HRNG (or sensors for TRNG) that can approach ludicrous bitrates, I've never had the luxury of one, and I'm not entirely sure I could be convinced the output was any "better" than a vetted arrangement from my second paragraph.
All of this is to say: okay but we already do that and massaging randomness to give us results we want is what all this modeling stuff ... is, so other than some off in the weeds magnetic film manipulation, I'm assuming that's modelled, too. It's just models all the way down?
Even tought the article is about true random number, pseudo random is more valuable for scientific simulations. In those simulations you don't typically want true randomness, you want a generator that pass a suite of randomness tests while having the ability to repeat that stream of numbers to replicate your experiment.
Sometimes, you even discard numbers so different simulation runs with different parameters consume the same amount of numbers. A simplistic example:
Sometimes, you even discard numbers so different simulation runs with different parameters consume the same amount of numbers. A simplistic example:
if rand()<.5 :
doSomethingWithRand(rand())
else:
doSomethingWithoutRand()
rand()> xor with each other, and use that to seed a cryptographically secure generator
Do not try to cook your moderate entropy data source. You can end up cooking what little entropy it had out of it.
Many CSPRNGs allow seeds of arbitrary size. Just push all of your sketchy data into it, and let the hash function handle scavenging the entropy for you.
Do not try to cook your moderate entropy data source. You can end up cooking what little entropy it had out of it.
Many CSPRNGs allow seeds of arbitrary size. Just push all of your sketchy data into it, and let the hash function handle scavenging the entropy for you.
Just because you said "psuedo" in all cases: it is "pseudo".
Completely off-topic: do you live alone in the forest, or with others?
Completely off-topic: do you live alone in the forest, or with others?
My phone never fails to find new ways to embarrass.
With others.
With others.
It is not embarrassing at all. :) I did not even want to comment on it initially, but then I thought I could help with it... That comment got down-voted already though.
If you do not mind me asking: is it a community? I swear I have been wanting to live in a community such as Twin Oaks Community but I am in Europe! :(
If you do not mind me asking: is it a community? I swear I have been wanting to live in a community such as Twin Oaks Community but I am in Europe! :(
> But, as Dr Aimone’s colleague Darby Smith notes, the real world that computer modellers are trying to model does not work like this. For example, the temperature in London in December may vary between -7°C and 17°C, but is most likely to be in the range 3°C to 8°C. [...] Distorting uniform distributions of random numbers to take account of these realities is tedious and unsatisfactory. As Dr Smith observes, it would be more efficient if the random numbers used corresponded to the natural distribution in the first place.
I have a hard time understanding how this is a problem. Using uniform random numbers to choose the x-axis value on a graph of an integrated probability distribution function and mapping it to the y-axis is pretty garsh darn simple and normal. This is the crux of monte carlo methods and is stupidly fast these days.
What are they talking about?
I have a hard time understanding how this is a problem. Using uniform random numbers to choose the x-axis value on a graph of an integrated probability distribution function and mapping it to the y-axis is pretty garsh darn simple and normal. This is the crux of monte carlo methods and is stupidly fast these days.
What are they talking about?
Though I agree we have good solutions to this, I also think it's a more nuanced problem than it seems at first glance. See for example this stack overflow post: https://stackoverflow.com/questions/75677/converting-a-unifo.... To convert uniform to a Gaussian there are at least four different competing methods, all with subtle tradeoffs. Besides that there are certainly other continuous distributions we might be interested in transforming to, which are useful but not as nice as a Gaussian.
> there are at least four different competing methods, all with subtle tradeoffs
So choose one at random for each sample :)
So choose one at random for each sample :)
> there are at least four different competing methods, all with subtle tradeoffs.
As is the case with most implementations of things, even elementary things, that have to do with the real numbers on discrete hardware (see numerical integration, square roots and inverses, trig functions, various approximations of the real numbers themselves, etc.).
Real numbers are hard. It's a blessing only a minority of computer programs need to actually deal with them (or their approximations).
As is the case with most implementations of things, even elementary things, that have to do with the real numbers on discrete hardware (see numerical integration, square roots and inverses, trig functions, various approximations of the real numbers themselves, etc.).
Real numbers are hard. It's a blessing only a minority of computer programs need to actually deal with them (or their approximations).
Methods to simulate a Normal distribution doesn’t really help you simulate a measured distribution of data, which was the stated problem, wasn’t it? The parent comment’s suggestion to use the tabulated Inverse Transform method is already likely to be the optimal choice for simulating a discrete data distribution. There’s one alternative called the Alias Method that is fast to sample, but uses a discontinuous mapping so it compromises your ability to benefit from stratified or Quasi-Random sampling, which means it loses significant efficiency for Monte Carlo applications and thus doesn’t get used very often. (This is true of Ziggurat as well, and aside from Ziggurat the SO page you linked only has two other decent suggestions and one of them is the Inverse Transform method. Box-Muller is historically interesting, but I think doesn’t really “compete”.) So, anyway, FWIW, it doesn’t really seem super nuanced. I’m guessing the article’s author was just writing for a non-technical audience and isn’t clearly stating the problems being investigated by the COINFLIPS team.
For what it's worth, I once struggled to implement random walks on custom hardware because its ISA lacked trig support and I couldn't generate N(0,1)s quickly enough. For that application, tens of fp32 maccs to transform from uniform data was a non-starter.
Producing large samples of uniform pseudo-random numbers in high dimensions is very tricky. If COINFLIPS can solve that problem then that would be very useful. That said, I don't know if there are many computational workloads where the basic random number generation step is the performance bottleneck.
Random scalars definitely don't seem like somethign that needs radical technical solutions, no. I wonder if the tricky part is in choosing random vectors?
Just doing simple things like choosing a uniformly distributed random point in a disk or on the surface of a sphere are awkward enough to do efficiently; choosing a bunch of random points drawn from the London temperature/pressure/rainfall distribution for December is much worse. I wonder if that might be part of the complexity that is being elided to bring this article to a popular-science-reader level?
Just doing simple things like choosing a uniformly distributed random point in a disk or on the surface of a sphere are awkward enough to do efficiently; choosing a bunch of random points drawn from the London temperature/pressure/rainfall distribution for December is much worse. I wonder if that might be part of the complexity that is being elided to bring this article to a popular-science-reader level?
> I wonder if the tricky part is in choosing random vectors?
Sampling vectors from multidimensional random distributions is a well studied problem. For example the open source project https://mc-stan.org implemented several (at the time) state of the art methods like Hamiltonian Monte Carlo with the help of Automatic Differentiation.
Sampling vectors from multidimensional random distributions is a well studied problem. For example the open source project https://mc-stan.org implemented several (at the time) state of the art methods like Hamiltonian Monte Carlo with the help of Automatic Differentiation.
Maybe? Sampling on a sphere is computationally trivial in spherical coordinates and done in every undergraduate Monte Carlo radiation transport class as a homework.
Knowing temperature PDFs is similarly easy, and so is sampling them.
I will have to go read some literature on this cointoss business I think.
Knowing temperature PDFs is similarly easy, and so is sampling them.
I will have to go read some literature on this cointoss business I think.
Yes, you can use an inverse CDF to implement a fairly efficient generator for pretty much any probability distribution. (I'm sure there's some pathological, and uncommon, counterexample.) It's just a small/quick lookup table, and you can interpolate if you need extra resolution.
Isn't the problem that the normal distribution doesn't have an (inverse) CDF in closed form? So even the most common non-uniform distribution becomes a pathological example.
https://en.wikipedia.org/wiki/Probit
https://en.wikipedia.org/wiki/Probit
Nope, that's not a problem. You don't need a closed form and simple equation to build the lookup table (inverse CDF). Use whatever expensive and iterative functions you want to build it.
For the normal distribution, you can use a bisection on the math.h erf() function to invert it. This is expensive, but you're only going to do it to make your lookup table once. Build that table to reasonably fit in your cache, and then use your uniform pseudo random integers to peak into that table.
As I mentioned above, you can interpolate between values in the table if you need more resolution. There are other tricks for specific distributions, but the technique is very general.
For the normal distribution, you can use a bisection on the math.h erf() function to invert it. This is expensive, but you're only going to do it to make your lookup table once. Build that table to reasonably fit in your cache, and then use your uniform pseudo random integers to peak into that table.
As I mentioned above, you can interpolate between values in the table if you need more resolution. There are other tricks for specific distributions, but the technique is very general.
You can approximate it and throw away some samples to get the true distribution. See https://en.wikipedia.org/wiki/Ziggurat_algorithm for one method which I believe statistical languages like R currently use to generate normal random variables.
I'm pretty sure the project is looking at physical devices to add to the entropy pool, and they talked about two examples (which do seem pretty neat).
> One relies on the patterns magnetic films make when disturbed, the other on how electrons travel through the barrier of a quantum-tunnelling diode. Both of these things are truly random.
The use of the Von Neumann quote, "Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin” is pretty annoying, given that he said it in defense of his PRNG. Sort of a tongue-in-cheek "yes this is fundamentally wrong (sinful) but I'm going to do it" sort of thing.