7 ms·

How Do Computers Generate Random Numbers?

65 points by aryamansharda 6y ago

mywittyname 6y ago
The chart shows the distribution of "10,000 dice rolls," yet each potential value, 1-6, has between 6000 and 7000 hits, indicating the true number of rolls to be between 36,000 and 42,000.
- aryamansharda 6y ago
  You're absolutely right. The attached code was for 40K and I just mislabeled the graph. I've updated it - thanks for catching that!
IIAOPSW 6y ago
My personal favorite RNG is the logistical map. x_{n+1} = 4x_n(1-x_n). There is no hidden seed beyond the current output. Thus if you have a scientific calculator that lets you refer to the value on screen then you can rig it into an RNG. Seeing a simple, non-programmable machine "misbehave" and act random melts my mind a little.
- kanzenryu2 6y ago
  You might find this ultra-simple RNG interesting https://en.wikipedia.org/wiki/Rule_30 https://en.wikipedia.org/wiki/Rule_30
- phreeza 6y ago
  Beware that while it looks random, this is actually not a great rng. For example, it does not satisfy the central limit theorem.
- bregma 6y ago
  That's still just a linear congruential PRNG with state sizeof(unsigned int). LCG is simple and has well-known flaws.
  - IIAOPSW 6y ago
    No it is not an LCG. When you distribute the terms there is a -4x_n^2. Therefore it is non-linear.
shadowprofile77 6y ago
Just out of layman's curiosity, what would be the problem or difficulty of somehow connecting a more compact type of radio telescope that detects some level of cosmic background radiation and hooking that up to a computer. Would this not be a guaranteed way of generating truly random numbers for any need flawlessly? I know that serious radio telescopes cost way more than any random person could afford to pay but I've certainly seen plans for smaller DIY homemade models.
- stingraycharles 6y ago
  You’re not too far off. There’s for example the Quantis random number generator, which uses photons: https://www.idquantique.com/random-number-generation/products/quantis-random-number-generator/ https://www.idquantique.com/random-number-generation/product... From the brochure: “ Photons - light particles - are sent one by one onto a semi-transparent mirror and detected. The exclusive events (reflection - transmission) are associated to « 0 » - « 1 » bit values.”
- mceachen 6y ago
  Any stochastic data source may not (and almost certainly isn't) evenly distributed--it'll probably follow some normal distribution. Your PRNG that reads from your telescope would need to compensate for this. As far as using radiation to generate random numbers, check out https://www.fourmilab.ch/hotbits/ https://www.fourmilab.ch/hotbits/
  - shadowprofile77 6y ago
    Your claim makes me a bit skeptical unless im misunderstanding something here... I'd assume that a data source of pure natural radiation would be genuinely random even if its distribution isn't even, and that using anything in your computer to compensate for it would actually do the opposite: reduce randomness with damaging bias. It reminds me of a story from Cryptonomicon in which a character mentions a secretary grabbing randomly spun number balls from a tumbling device while blindfolded (if I remember the objects right) and not liking the results when she had to write them down because they didn't look random enough to her, so she starts peeking and slightly "correcting", and thus ruins a number of one-time pads
rurban 6y ago
The Mersenne-Twister approach should certainly not be studied anymore, even if some popular old libraries still use it. It fell long out of favor, is too slow, and not good enough. Modern PRNG's can be tested with Dieharder, TestU01 or STS and benchmarked. This article only talks about primitive old LCG's (not any good one) or MT.
- aryamansharda 6y ago
  When you say Mersenne-Twister isn't good enough, what are the other shortcomings apart from speed? It seems that even modern versions of Python are continuing to use it...
  - Straw 6y ago
    Its slow, large, and statistically worse than modern PRNGs- and jumping ahead takes longer and a more complicated algorithm. Even a truncated 128-bit LCG has far better properties. See https://www.pcg-random.org/index.html https://www.pcg-random.org/index.html The homepage might come across as a a little overzealous (for example ChaCha quality listed as good rather than excellent), but generally has good points.
    - benibela 6y ago
      However, this page claims PCG is rather bad: http://pcg.di.unimi.it/pcg.php http://pcg.di.unimi.it/pcg.php They recommend to use their xoshiro PRNG.
      - Straw 6y ago
        That author has a history of extreme bias and almost-vindictive personal attacks on the author of PCG. See the reddit comments: https://www.reddit.com/r/programming/comments/8jbkgy/the_wrapup_on_pcg_generators/ https://www.reddit.com/r/programming/comments/8jbkgy/the_wra... And the PCG author's response: https://www.pcg-random.org/posts/on-vignas-pcg-critique.html https://www.pcg-random.org/posts/on-vignas-pcg-critique.html For example, for one of his arguments, he specifically chose a generator called pcg32_once_insecure, which the PCG author does not recommend due to its invertible output function! Personally, I have read both arguments in detail and I would always use PCG or even a truncated LCG over xoshiro, which has a large size in comparison, potentially worse statistical properties, and no gain- faster in some benchmarks and slower in others.
ImaCake 6y ago
For those interested, one can get from a uniform distribution to pretty much any defined statistical distribution using just the uniform random number generator and the inverse cumulative distribution function of the desired random distribution. A useful trick for non-standard distributions with no function available in your prefered language. Example from matlab: https://www.mathworks.com/help/stats/generate-random-numbers-using-the-uniform-distribution-inversion-method.html https://www.mathworks.com/help/stats/generate-random-numbers...
lsc36 6y ago
1. You don't turn PRNG into "true" RNGs simply by picking seeds from environmental randomness. The seed is just the initial state, as long as the output is generated by a deterministic algorithm, by definition it's a PRNG. At the very best you can make a CSPRNG, but not a "true" RNG. 2. The dice roll example is not uniform distribution, I think this is a common pitfall when generating random integers of a range. `randomNumber % 6` results in a slight bias towards 0 and 1, since 2^31 % 6 == 2, there are more numbers in the range [0, 2^31-1] that map to 0 and 1 than those that map to 2...5. To make it uniform, for example, you should always discard if `randomNumber < 2` and regenerate another number for use.
- atg_abhishek 6y ago
  Ah very true, an often ignored thing, thank you for sharing!
- ficklepickle 6y ago
  #2 reminds me of Benford's Law, which I recently learned about and find truly fascinating. https://en.wikipedia.org/wiki/Benford%27s_law https://en.wikipedia.org/wiki/Benford%27s_law
  - chriselles 6y ago
    Interesting. On first pass, Benford’s Law looks a lot like Zipf’s Law. What differentiates Benford’s Law from Zipf’s Law?
    - pmiller2 6y ago
      From https://en.wikipedia.org/wiki/Zipf%27s_law https://en.wikipedia.org/wiki/Zipf%27s_law : > It has been argued that Benford's law is a special bounded case of Zipf's law,[22] with the connection between these two laws being explained by their both originating from scale invariant functional relations from statistical physics and critical phenomena.[24] The ratios of probabilities in Benford's law are not constant. The leading digits of data satisfying Zipf's law with s = 1 satisfy Benford's law.
jrnkntl 6y ago
Cloudflare has a fun solution to this involving lava lamps[0][1] [0] https://blog.cloudflare.com/randomness-101-lavarand-in-production/ https://blog.cloudflare.com/randomness-101-lavarand-in-produ... [1] https://blog.cloudflare.com/lavarand-in-production-the-nitty-gritty-technical-details/ https://blog.cloudflare.com/lavarand-in-production-the-nitty...
cm2187 6y ago
Is a hardware random number generator that would use environment or electrical sensors to generate noise expensive or hard to manufacture? I would assume this should be part of any standard motherboard given the importance of cryptography. Or does it create an attack vector?
- Joker_vD 6y ago
  Why, of course, it's been there for almost 8 years already in Intel processors: https://en.wikipedia.org/wiki/RDRAND https://en.wikipedia.org/wiki/RDRAND
- jlgaddis 6y ago
  There was an RNG on the i810 chipset ~20 years or so ago and several VIA chips had onboard RNGs as well. Modern chips ranging from the one in the Raspberry Pi to Intel CPUs have them too.
- jfindley 6y ago
  Cryptography doesn't depend on random numbers for its random seed. It depends on unpredictable numbers. These are not the same thing. As long as no-one can predict what the next number will be it doesn't matter how "random" they are. TFA is sufficiently vague it's unclear if the author understands this. The more I read it, the more confused the article appears to be (e.g. mersenne twister is NOT a good example of a modern or high quality PRNG). For more about secure random numbers in Linux, I'd suggest reading [0]. 0: https://buttondown.email/cryptography-dispatches/archive/cryptography-dispatches-the-linux-csprng-is-now/ https://buttondown.email/cryptography-dispatches/archive/cry...
  - UncleMeat 6y ago
    I wouldn't be so universal with this statement. Some cryptosystems really do need uniform randomness (ECDSA) rather than just negligible probability of choosing values. Other cryptosystems depend on not reusing values, though the values could be predictable. Sometimes there are subtle shifts in these needs based on modes (AES/CBC vs AES/GCM is a good example).
setereklakshit 6y ago
I keep finding this solution and yet this is works best for me
johnatwork 6y ago
Roll20 has an interesting way of generating random numbers as well - https://wiki.roll20.net/QuantumRoll https://wiki.roll20.net/QuantumRoll
mschuetz 6y ago
My favourite is this one: https://preshing.com/20121224/how-to-generate-a-sequence-of-unique-random-integers/ https://preshing.com/20121224/how-to-generate-a-sequence-of-... * Creates a sequence of unique integers * Uses prime numbers that are congruent to P = 3 (mod 4). * A single iteration has noticable patterns but applying it twice already results in randomness that is sufficiently good for many use cases. * It is "embarrassingly parallel", a simple mapping of randomValue = randomize(i). You can calculate unique and deterministic random numbers from input i in parallel threads with no sync between threads. * Since it is a unique mapping of i to r, you can use it to shuffle data sets virtually instantly. Take the index of a value in the original array, and use it to compute the target index in the shuffled array. * I've used it to shuffle up to 800 million items per second on a GPU, including the time it took to transfer the data from RAM to GPU. So without the IO, you could probably shuffle billions of values per second, probably mostly bound by GPU bandwidth. E.g., 700GB/s and each item is 70 bytes -> could perhabs shuffle 10 billion items per second.

65 points by aryamansharda 6y ago

The chart shows the distribution of "10,000 dice rolls," yet each potential value, 1-6, has between 6000 and 7000 hits, indicating the true number of rolls to be between 36,000 and 42,000.

aryamansharda 6y ago
You're absolutely right. The attached code was for 40K and I just mislabeled the graph. I've updated it - thanks for catching that!

IIAOPSW 6y ago

My personal favorite RNG is the logistical map. x_{n+1} = 4x_n(1-x_n). There is no hidden seed beyond the current output. Thus if you have a scientific calculator that lets you refer to the value on screen then you can rig it into an RNG. Seeing a simple, non-programmable machine "misbehave" and act random melts my mind a little.

kanzenryu2 6y ago
You might find this ultra-simple RNG interesting https://en.wikipedia.org/wiki/Rule_30 https://en.wikipedia.org/wiki/Rule_30
phreeza 6y ago
Beware that while it looks random, this is actually not a great rng. For example, it does not satisfy the central limit theorem.
bregma 6y ago
That's still just a linear congruential PRNG with state sizeof(unsigned int). LCG is simple and has well-known flaws.
- IIAOPSW 6y ago
  No it is not an LCG. When you distribute the terms there is a -4x_n^2. Therefore it is non-linear.

shadowprofile77 6y ago

Just out of layman's curiosity, what would be the problem or difficulty of somehow connecting a more compact type of radio telescope that detects some level of cosmic background radiation and hooking that up to a computer. Would this not be a guaranteed way of generating truly random numbers for any need flawlessly? I know that serious radio telescopes cost way more than any random person could afford to pay but I've certainly seen plans for smaller DIY homemade models.

stingraycharles 6y ago
You’re not too far off. There’s for example the Quantis random number generator, which uses photons: https://www.idquantique.com/random-number-generation/products/quantis-random-number-generator/ https://www.idquantique.com/random-number-generation/product... From the brochure: “ Photons - light particles - are sent one by one onto a semi-transparent mirror and detected. The exclusive events (reflection - transmission) are associated to « 0 » - « 1 » bit values.”
mceachen 6y ago
Any stochastic data source may not (and almost certainly isn't) evenly distributed--it'll probably follow some normal distribution. Your PRNG that reads from your telescope would need to compensate for this. As far as using radiation to generate random numbers, check out https://www.fourmilab.ch/hotbits/ https://www.fourmilab.ch/hotbits/
- shadowprofile77 6y ago
  Your claim makes me a bit skeptical unless im misunderstanding something here... I'd assume that a data source of pure natural radiation would be genuinely random even if its distribution isn't even, and that using anything in your computer to compensate for it would actually do the opposite: reduce randomness with damaging bias. It reminds me of a story from Cryptonomicon in which a character mentions a secretary grabbing randomly spun number balls from a tumbling device while blindfolded (if I remember the objects right) and not liking the results when she had to write them down because they didn't look random enough to her, so she starts peeking and slightly "correcting", and thus ruins a number of one-time pads

rurban 6y ago

The Mersenne-Twister approach should certainly not be studied anymore, even if some popular old libraries still use it. It fell long out of favor, is too slow, and not good enough. Modern PRNG's can be tested with Dieharder, TestU01 or STS and benchmarked. This article only talks about primitive old LCG's (not any good one) or MT.

aryamansharda 6y ago
When you say Mersenne-Twister isn't good enough, what are the other shortcomings apart from speed? It seems that even modern versions of Python are continuing to use it...
- Straw 6y ago
  Its slow, large, and statistically worse than modern PRNGs- and jumping ahead takes longer and a more complicated algorithm. Even a truncated 128-bit LCG has far better properties. See https://www.pcg-random.org/index.html https://www.pcg-random.org/index.html The homepage might come across as a a little overzealous (for example ChaCha quality listed as good rather than excellent), but generally has good points.
  - benibela 6y ago
    However, this page claims PCG is rather bad: http://pcg.di.unimi.it/pcg.php http://pcg.di.unimi.it/pcg.php They recommend to use their xoshiro PRNG.
    - Straw 6y ago
      That author has a history of extreme bias and almost-vindictive personal attacks on the author of PCG. See the reddit comments: https://www.reddit.com/r/programming/comments/8jbkgy/the_wrapup_on_pcg_generators/ https://www.reddit.com/r/programming/comments/8jbkgy/the_wra... And the PCG author's response: https://www.pcg-random.org/posts/on-vignas-pcg-critique.html https://www.pcg-random.org/posts/on-vignas-pcg-critique.html For example, for one of his arguments, he specifically chose a generator called pcg32_once_insecure, which the PCG author does not recommend due to its invertible output function! Personally, I have read both arguments in detail and I would always use PCG or even a truncated LCG over xoshiro, which has a large size in comparison, potentially worse statistical properties, and no gain- faster in some benchmarks and slower in others.

ImaCake 6y ago

For those interested, one can get from a uniform distribution to pretty much any defined statistical distribution using just the uniform random number generator and the inverse cumulative distribution function of the desired random distribution. A useful trick for non-standard distributions with no function available in your prefered language. Example from matlab: https://www.mathworks.com/help/stats/generate-random-numbers-using-the-uniform-distribution-inversion-method.html https://www.mathworks.com/help/stats/generate-random-numbers...

lsc36 6y ago

1. You don't turn PRNG into "true" RNGs simply by picking seeds from environmental randomness. The seed is just the initial state, as long as the output is generated by a deterministic algorithm, by definition it's a PRNG. At the very best you can make a CSPRNG, but not a "true" RNG. 2. The dice roll example is not uniform distribution, I think this is a common pitfall when generating random integers of a range. `randomNumber % 6` results in a slight bias towards 0 and 1, since 2^31 % 6 == 2, there are more numbers in the range [0, 2^31-1] that map to 0 and 1 than those that map to 2...5. To make it uniform, for example, you should always discard if `randomNumber < 2` and regenerate another number for use.

atg_abhishek 6y ago
Ah very true, an often ignored thing, thank you for sharing!
ficklepickle 6y ago
#2 reminds me of Benford's Law, which I recently learned about and find truly fascinating. https://en.wikipedia.org/wiki/Benford%27s_law https://en.wikipedia.org/wiki/Benford%27s_law
- chriselles 6y ago
  Interesting. On first pass, Benford’s Law looks a lot like Zipf’s Law. What differentiates Benford’s Law from Zipf’s Law?
  - pmiller2 6y ago
    From https://en.wikipedia.org/wiki/Zipf%27s_law https://en.wikipedia.org/wiki/Zipf%27s_law : > It has been argued that Benford's law is a special bounded case of Zipf's law,[22] with the connection between these two laws being explained by their both originating from scale invariant functional relations from statistical physics and critical phenomena.[24] The ratios of probabilities in Benford's law are not constant. The leading digits of data satisfying Zipf's law with s = 1 satisfy Benford's law.

jrnkntl 6y ago

Cloudflare has a fun solution to this involving lava lamps[0][1] [0] https://blog.cloudflare.com/randomness-101-lavarand-in-production/ https://blog.cloudflare.com/randomness-101-lavarand-in-produ... [1] https://blog.cloudflare.com/lavarand-in-production-the-nitty-gritty-technical-details/ https://blog.cloudflare.com/lavarand-in-production-the-nitty...

cm2187 6y ago

Is a hardware random number generator that would use environment or electrical sensors to generate noise expensive or hard to manufacture? I would assume this should be part of any standard motherboard given the importance of cryptography. Or does it create an attack vector?

Joker_vD 6y ago
Why, of course, it's been there for almost 8 years already in Intel processors: https://en.wikipedia.org/wiki/RDRAND https://en.wikipedia.org/wiki/RDRAND
jlgaddis 6y ago
There was an RNG on the i810 chipset ~20 years or so ago and several VIA chips had onboard RNGs as well. Modern chips ranging from the one in the Raspberry Pi to Intel CPUs have them too.
jfindley 6y ago
Cryptography doesn't depend on random numbers for its random seed. It depends on unpredictable numbers. These are not the same thing. As long as no-one can predict what the next number will be it doesn't matter how "random" they are. TFA is sufficiently vague it's unclear if the author understands this. The more I read it, the more confused the article appears to be (e.g. mersenne twister is NOT a good example of a modern or high quality PRNG). For more about secure random numbers in Linux, I'd suggest reading [0]. 0: https://buttondown.email/cryptography-dispatches/archive/cryptography-dispatches-the-linux-csprng-is-now/ https://buttondown.email/cryptography-dispatches/archive/cry...
- UncleMeat 6y ago
  I wouldn't be so universal with this statement. Some cryptosystems really do need uniform randomness (ECDSA) rather than just negligible probability of choosing values. Other cryptosystems depend on not reusing values, though the values could be predictable. Sometimes there are subtle shifts in these needs based on modes (AES/CBC vs AES/GCM is a good example).

setereklakshit 6y ago

I keep finding this solution and yet this is works best for me

johnatwork 6y ago

Roll20 has an interesting way of generating random numbers as well - https://wiki.roll20.net/QuantumRoll https://wiki.roll20.net/QuantumRoll

mschuetz 6y ago

My favourite is this one: https://preshing.com/20121224/how-to-generate-a-sequence-of-unique-random-integers/ https://preshing.com/20121224/how-to-generate-a-sequence-of-... * Creates a sequence of unique integers * Uses prime numbers that are congruent to P = 3 (mod 4). * A single iteration has noticable patterns but applying it twice already results in randomness that is sufficiently good for many use cases. * It is "embarrassingly parallel", a simple mapping of randomValue = randomize(i). You can calculate unique and deterministic random numbers from input i in parallel threads with no sync between threads. * Since it is a unique mapping of i to r, you can use it to shuffle data sets virtually instantly. Take the index of a value in the original array, and use it to compute the target index in the shuffled array. * I've used it to shuffle up to 800 million items per second on a GPU, including the time it took to transfer the data from RAM to GPU. So without the IO, you could probably shuffle billions of values per second, probably mostly bound by GPU bandwidth. E.g., 700GB/s and each item is 70 bytes -> could perhabs shuffle 10 billion items per second.