Shutterfly Interview Question
Software Engineer / DevelopersCountry: United States
randomness can be predicted while pseudo random nos can be predicted... follow pari library of math for more details and functions
Random numbers are simply numbers which doesn't obey any reason.
Its basically like, at an instant a number comes to your mind for no reason.
Pseudo random numbers, are numbers generated using algorithm with high degree of randomness. Since machine can't simply come up with any number, the cases where we need random numbers for computers, we use random number generator algorithms, and the number they generate are called pseudo random number.
hope this helps
The long post sums things up very nicely.
The existence of randomness is an undecided (and possibly undecidable) philosophical question. Assuming tiny particles do indeed behave randomly, we can do measurements on them to create "true" random generators.
Binary-logic based computers (the ones we have now) are entirely non-random. The way we generate pseudo-random numbers on them is by divisibility tricks. (Or other tricks, for that matter. Such as looking at the clock with high precision.) Namely, if you find some large prime, you can easily iterate over all numbers smaller than it in a manner that looks random, but isn't.
On a classical computer, it's impossible to write code to generate truly random numbers without access to a physical device that can do it, such as a quantum device or other physical source of randomness. This is because classical computers are deterministic: the future state of a machine is entirely determined by its current state.
- eugene.yarovoi August 08, 2012For this reason, classical computers use PRNGs (pseudo-random number generators). These use some complicated arithmetic to deterministically generate sequences of numbers that appear random. Often, the next "random" number is generated by applying some function to the previous "random" number, with the first random number being taken from the system time or something like that. To someone who doesn't know the pattern and doesn't time the launch of the program to the nanosecond, the numbers appear random and usually behave as if they were random. To understand this concept, search Wikipedia for "Middle Square Method", a very simple method for generating random numbers (that is quite flawed -- I only recommend it for understanding the concept of pseudo-random generation, not for actually implementing PRNGs). If you want serious methods for pseudo-random number generation, look up "linear congruential generator", "Mersenne Twister", and "Blum Blum Shub" (these are just examples; there are many more). Out of the three I named, all but the linear congruential generator are nontrivial to understand mathematically.
As for true randomness, it's actually not even known for certain whether true randomness even exists. We believe certain events, such as quantum mechanical observations, to be truly random, but as we do not fully understand quantum mechanics, we can't say for certain. Processes like dice rolls are not really random, but may be indistinguishable from randomness because tiny, unobservable changes in the initial state of the system translate into huge differences in outcomes. There is a whole field of physics / mathematics / mathematical physics called Chaos Theory that studies such sensitivity to initial values. Chaos Theory sounds really cool and actually is. It also has sister topics called great names like Bifurcation Theory and Catastrophe Theory.
In any event, you can't give an algorithm to produce truly random bits. What you can try to do is access some external source of data that is in no way related to your program and that will thus hopefully appear random. If you access a quantum pool it might be truly random. Otherwise, you could use time between packet delays on your local network, mapped in some way to a specific range, as random numbers. If your computer has wireless, you might be able to use delays between various signals you pick up from surrounding networks. You might be able to use thermal noise. Or noise in radio signals. There are many possible ideas here, but an important thing to keep in mind is that many environmental factors can be manipulated by an attacker, so one should be careful when using data from the environment as a source of randomness in applications whose security depends on the random numbers being unpredictable.
Finally, you could always return digits of pi. Though obviously not truly random (since they can be calculated by a formula), as far as I know, they pass every typical statistical test for randomness.