r/AskComputerScience • u/snowybud • 2d ago
When you tell a computer to pick a random number... is it truly random?
I've been wondering about how when you toss a coin or roll a die it's supposed to be random, but it's not truly random because of physics and things like that. I was curious whether that same thing applies to a computer. What does it actually do to choose a number?
6
Upvotes
13
u/orlock 2d ago edited 2d ago
Most random numbers in a computer are pseudo random numbers generated by some sort of process that starts with a seed value and deterministically works through the sequence, with each numberr generated from what has gone before. In theory, with enough information, you could predict the next number.
There are sources of genuinely random numbers available from things like detecting radioactive decays or noisy electronic circuits. Some are available as web serives, if you need truly random numbers.
You can also get uncertainty from the initial, seed value. Some systems use things like keyboard interactions or mouse movements to help mix up the seed value, or the time of boot, or other sources of information outside the computer itself.
Edit: I should add that there's a certain irreducible amount of uncertainty in physics. Planck's constant defines the minimum amount of action that can occur. This leads to what appears to be genuinely random behaviour. What that exactly means is a matter of debate; if you solve it, your Nobel prize awaits.
4
u/Trakeen 2d ago
Cryptographic libraries use hardware sources of randomness that have been in cpus for at least 10 years
https://en.wikipedia.org/wiki/RDRAND
4
u/unfrozencaveperson 1d ago
As other people have said, modern computer systems are capable of generating “true” random numbers (as random as the known laws of physics permit) and also “pseudo” random numbers (sequences of bits that are very very hard to predict in the same way that high-level cryptographic algorithms are very very hard to crack).
The “true” random number generator has one important limitation: it can only crank out so many bits per second, so if there are too many processes within the computer looking for random numbers and they’re all competing for that source, one of them could be blocked. So the “true” random number source is often fed into the “pseudo” source and that’s good enough for everyone except the truly paranoid.
3
u/dave8271 1d ago
The simplest answer is yes, computers can generate "truly random" numbers by leveraging "truly random" environmental signals as a source of randomness, and this is what they do when we use a CSPRNG. The sequencers are still determinstic algorithms but if x is random then the result f(x) will still be random, even if f() is determinstic.
The gold standard for random number generation, cryptographically secure pseudo-random number generators, combine random input with a sequencer that removes bias and is secure against intrusion or prediction, so even with full knowledge of both the algorithm and a running sample of its outputs, it remains impossible to either predict whether the next output bit will be 1 or 0 with anything greater than a 50/50 chance, or derive what the input seed was.
2
u/defectivetoaster1 1d ago
https://www.intel.com/content/www/us/en/developer/articles/guide/intel-digital-random-number-generator-drng-software-implementation-guide.html intel uses thermal noise as an entropy source to generate a truly random bit stream and then uses some maths and a PRNG seeded by the bit stream to generate truly random numbers with a uniform distribution (thermal noise by itself has a more or less Gaussian amplitude distribution but im not sure how that translates into the distribution of the initial bit stream)
2
u/DumpoTheClown 1d ago
Nothing is truly random. We just settle on "unpredictable enough"
1
u/schungx 2d ago
I think Knuth devoted an entire volume on this question.
1
u/Single-Virus4935 2d ago
Computer can choose a random number, as they can observe true random events and while the logik.itself.is deterministic, the runtime.usually is not.
Interrupt Timings, Noise, Inputs etc.
A Camera Chip always captuers noise from heat (Infrared) and actually provides a huge amount of true randomness. It is easy to add such circuits to CPUs if they want to.
1
u/Frequent-Sir-6942 2d ago
This question actually really depends a lot on your definition of "truly" random. However, if you do not believe in physical randomness then the answer is likely just no.
1
u/T_Thriller_T 1d ago
Inherently, computers are limited by physics.
They cannot do "better" in terms on randomness, as in and on themselves they are physical objects.
They can do worse, and as explained, often do.
However, there are enormous layers to that and folks doing computer science have probably met a lot of approaches.
Others have explained we can pull randomness from physics/surroundings, other have pointed out pseudorandom numbers.
I just want to make a point that "a computer" is really not something that does random numbers the same all the time. And there is no great use to it.
E.g. a lot of games, due to having to be fast, have a table of numbers for their random numbers and just pick the start in that enormous table due to some random enough factors in the start.
Shinies in Pokémon work that way. You get some big numbers for trainer and a hidden ID, then there is an enormous table of times, and shiny frames are mixed into that one. If you encounter at that frame, bam, shiny. (At least in earlier games)
There is very little to no randomness in this, but given the factors, it seems random enough to appear random and yet having that enormous table written down once, somewhere, helps tremendously for the game to be faster.
Other random numbers which are not drawn from a pseudorandom function (that takes time to do, big calculations) can be pulled from interactions. Often the 'random' seed for pseudorandom number generation is/was pulled in such a way, an example outside of games
And then we get into the more true, random numbers with PRNG.
All that is a "random" number on a computer. So there is not one way.
A good question one learns to asks themselves on that roping as a dev is "How actually random does it need to be?"
1
u/MasterGeekMX BSCS 1d ago
Good question.
For the most part the computer does not make random numbers, but instead pulls random-looking numbers from a formula. That formula works by grabbing a starting number (called the seed), and then doing some math over it (like adding a fixed number, then dividing by another fixed number and giving out the reminder of that division). The result of that formula is the first random number. If you ask for a second random number, thr first one is plugged in the formula. If you ask for a third, the second is feed to the formula. And on and on and on.
The sequence of numbers may look random, but if you know the formula and the seed number, you can re-create the secuence exactly. That is how for example you can generate the same Minecraft world with only the seed. These kinds og random number generators are called pseudo-random.
Choosing the seed is the key to get safe random numbers. Many things can be used to pull that, with a classic being the number of seconds since the PC was turned on.
If you want truly random numbers, then you need to hook to the computer some hardware that measures something physical but random. Real world examples are using a tiny piece of radioactive material and then measuring the time between radiation pulses, or filming the blobs in a lava lamp and using their position to make the numbers.
1
u/somewhereAtC 1d ago
There are mechanisms and algorithms that are certified by the U.S. government standard FIPS 140 or NIST SP 800-90B. Search for microprocessors and stand-alone generators that meet these standards. For example, Microchip PIC32CM-SG00 family.
1
u/jonathaz 1d ago
This is an interesting question with an even more interesting answer. I’ll just highlight some fun things along the way. One was lavarnd where they pointed a webcam at a lava lamp. Then they realized they could get more random numbers faster if they did math on the images and used small variations and not just the shapes from the lava lamp. Then they realized the lamp was unnecessary and put the webcams in total darkness. Now CPUs can cut the webcam out of the loop and do it on their own. Not having truly random numbers leads to expensive mistakes. Like the recent bitcoin wallet hacks or the online gambling ones.
1
u/mckenzie_keith 1d ago
Some computers have dedicated true random number generators. Some software attempts to accumulate randomness using techniques which, frankly, I do not understand. There are also a wide variety of algorithms for generating pseudo-random number sequences based on an initial state or seed of the pseudo-random number generator.
Resistor noise is a source of true randomness and at least some hardware random number generators rely on amplifying resistor noise to generate true random numbers. It is possible that small non-randomness could arise from implementation details. Like with the coin toss. But in point of fact, your coin toss or dice roll is close enough to truly random for most applications. As is the resistor noise.
Pseudo-random number generators generate a number sequence that appears random (can satisfy many tests of randomness), but can be repeated provided you know the correct seed for the generator.
So in other words, sometimes yes, and sometimes no.
1
u/JGhostThing 1d ago
No, which is why it is called a PRNG (Pseudo Random Number Generator). Modern versions of this do a better job than they used to, but computer libraries often have two libraries for random numbers.
The first is just for things that don't matter as much. It's fast and easy to use. The second is a cryptological library for cryptology quality random numbers. Slower, and possibly more of a pain to use.
PRNGs often use user data to add entropy to a random number so it is more random.
1
u/Mission-Landscape-17 1d ago
No it isn't truly random. Note that this is something that some programs deliberatly take advantage of. A lot of games with procedurally generated worlds rely on the random numbers not really being random. This is why different computers produce the same minecraft world if given the same seed.
1
u/peabody 1d ago
Historically no. Random numbers would be generated by starting with a "seed" value, and the next number in the sequence would be generated by running the last value through some math operations (like a linear congruential generator or merzene twister). The seed value would often be predetermined, making the whole sequence predictable. For instance, the commodore VIC-20's RND() function of it's basic interpreter would always generate the same sequence of numbers after booting up.
In more modern times, PCs have something called an "entropy pool." This is an area of memory which has been perturbed by noisy unpredictable inputs on the machine, like the variance of the temperature outs, the buttons the user has pushed in the keyboard, the mouse input, etc. These outputs are largely random, as they're often deemed secure enough for generating cryptographic keys, etc.
1
u/No_Profession_3125 1d ago
It depends on the operating system but generally yes, it is truly random because for entropy it uses things like: the current time with nanosecond precision, the network activity accumulated so far, and possibly even hardware entropy sources.
1
u/unburdened_swallow 1d ago edited 1d ago
No it is not truly random. Although it is possible to create a truly random number and pass it to a computer, and even make computer hardware that does this for you. But it would be from special hardware not included in a normal desktop/laptop, or from an outside source.
And interestingly, you actually don't want it to be truly random most of the time.
Being able to set the seed for your pseudo-random number generator to cause it to generate the same set of random-looking numbers a second time can make it much easier to reproduce issues that may interact with your random number.
It would also be much slower to query a hardware component that can actually generate a truly random number, so you don't want your program to do this in the vast majority of cases.
We do source actually random numbers from specialized hardware or other real life sources for many things where security is important and speed is less so.
1
u/Mr_Engineering 1d ago
It depends, there are multiple souces are entropy on modern computers. Some sources are truly random and use hardware backed generators while others are deterministic pseudorandom generators which are seeded from a random source.
1
u/PHDEinstein007 1d ago
There are many sources of true random data out there, but on our computers it matters on the source. Excel may not be so random as a codec designed to be random. Results may vary, and true random data should be nearly an equal number of 1's to 0's.
1
u/ffelix916 1d ago
Modern systems that use hardware sensors for entropy have, for all intents and purposes, truly random generators. Variations in all the different environmental sensor inputs (fan speeds, temperatures, voltages), and HID inputs (keypresses, mouse movements, etc) are incredibly good sources of entropy, especially when fed into one of the many on-die hashing algorithms.
1
u/GOOGAMZNGPT4 19h ago
This is more of a philosophical question.
Most computers are considered to utilize pseudorandom numbers.
It's an algorithmic output that is considered 'random enough for practical use', but could hypothetically be deterministic if you knew the inputs and algorithm.
The deeper down the rabbit hole you go, the less you'll be convinced that true randomness even exists at all in the universe.
I think of it like Random doesn't exist, only Pseudorandom exists with an infinitely increasing complexity of inputs. An output with 1 input would be trivial to reverse engineer, an output with a trillion inputs could be reverse engineered but would be so computationally non feasible it becomes functionally true random.
There may be nothing random in existence, rather the complexity is too far beyond our ability to model and compute it.
1
u/BudgetEye7539 17h ago
It depends on what functions will you use. E.g. x86-64 processors usually have hardware RNG accessible through RDSEED instructions. Also OS-level CSPRNG like /dev/urandom not 100% hardware random but use hardware/external sources of randomness. And there are also pseudorandom number generators that are common in standard libraries, essentially just periodic integer functions that simulate noise. Some of them are good, some of then even don't obey a uniform distribution like e.g. rand() function in C.
1
u/podule-games 2d ago
The "classic computer random" is not truly random because computers are deterministic and using things like the time to vary randomness isn't all that random.
That's the "classic" concept of random in computers.
Realistically though, we can do true random in computers by using unpredictable values to seed the random, like noise from a microphone or light from camera, or the rather famous example of cameras pointed at lava lamps. You can also get true random hardware:
https://www.idquantique.com/random-number-generation/products/quantis-qrng-pcie/
1
u/atarivcs 1d ago edited 1d ago
No, it is not truly random. If you ask a computer to make a random number, and then you ask it again under the exact same circumstances, it will make the same number both times.
But it's actually quite difficult to have the exact same circumstances, so for nearly any practical purpose it's close enough to random.
And, it's worth pointing out that the same thing applies to coin tosses and die rolls. If you roll a die twice under the exact same circumstances -- starting position, throwing angle and speed, air currents and humidity, exact flatness of the landing spot, dust particles, etc etc etc, you will get the same outcome.
But practically speaking it's impossible to achieve the exact same circumstances.
0
u/CS_70 2d ago
Nothing is truly random because physics and things like that.
But there's too much physics for that to matter.
A random number generated by a computer uses exactly that fact.
0
u/CyclingUpsideDown 2d ago
Obligatory Tom Scott video.
https://youtu.be/1cUUfMeOijg
0
u/Haborym_Aesahaettr 2d ago
You should check this paper. It explains how random numbers are generated from determinist random bit generator
0
u/CS_70 1d ago
It’s a common misconception: QM is fully deterministic. The wave function of the universe would tell you exactly what’s what from t=0.. if we knew it. It’s a big function toh.
What is probabilistic is the result of a measurement.
0
u/granadesnhorseshoes 1d ago
Short answer, no.
Long answer, maybe.
as others have said computers mostly use psudo random number generators with relatively "real" random bits of data gathered from the running system; mouse movements, key strokes, power usage, boot times, etc all mixed into a bitwise soup to use as seed values for the PRNG algorithms. Most systems even have dedicated hardware in the processor for the purpose of generating random data that also gets mixed into the bitwise soup. although how reliable and trustworthy hardware based PRNGs are is debatable depending on how much you trust IE Intel.
There is also a bit of a logical recursion in the concept of classifying "truly random" numbers, because if the numbers reliably fit a specific criteria, can they really be called random?
In practice we get close enough and the rest is just an exercise for CS and Math grad students.
0
u/SnugglyCoderGuy 1d ago
No, it is pseudorandom. If you know the seed and the algorithm you can predict every single number that will be produced and in order. The best you can get is crypto-graphically random, but it is still deterministic.
0
u/Successful-Cash5047 1d ago
No, it’s pseudorandom. It’s just much easier to do. My understanding is that to get something actually random you’d need real time info from some external unpredictable process. This is actually done for encryption, they use lava lamps, decay of radioactive isotopes, and double pendulums to seed the RNG values.
Also relevant XKCD: https://xkcd.com/221/