Sign in to follow this  
Peter Conn

True Random Numbers

Recommended Posts

Hiya I was talking to my maths teacher, and we're currently doing statistics and picking samples using random number tables and we came onto the point "How are random numbers generated?" - I know that computers make pseudorandom numbers using some sort of table and an algorithm and I've also heard that humans are useless with random numbers (stuff like subconcious decisions and picking the number 7 too much), so is there any way to get true random numbers? Also if anyone could explain to me a bit more indepth about computers pseudorandom numbers I'd be very grateful.

Share this post


Link to post
Share on other sites
It's my understanding that random numbers are generated predictably from a seed value, which is typically the previous random number. The first random number is often generated from the time at that moment. Therefore, the numbers are predictable provided you have enough information on the system.

Other attempts to create less predictable random numbers have involved everything from line noise, quantum state measurements, ground vibrations, and cosmic rays.

Share this post


Link to post
Share on other sites
The name "random number generator" is actually a bit of a misnomer. Pseudo-random number is better, seeing as on a computer you can't actually generate random numbers. It's important to remember the difference between something that we can't predict, and something that's truly random(read a good article about it somewhere). You can use the time, unique identifiers based on the specific computer, whatever you want, but it's all completely deterministic. Mersenne twister tends to come up a lot.

Share this post


Link to post
Share on other sites
CPU temp, inter-thread timing (as taken from the CPU clock), unitilized variables (not very good, but you might as well use it), elapsed time since last user action (mouse click, button press, etc), anything variable and "undefined" that won't crash your system...

Share this post


Link to post
Share on other sites
Quote:
Original post by DaBookshah
The name "random number generator" is actually a bit of a misnomer. Pseudo-random number is better, seeing as on a computer you can't actually generate random numbers. It's important to remember the difference between something that we can't predict, and something that's truly random(read a good article about it somewhere). You can use the time, unique identifiers based on the specific computer, whatever you want, but it's all completely deterministic. Mersenne twister tends to come up a lot.

It could be argued that everything is deterministic, so "random number generator" would be appropriate (depending on your viewpoint).

Share this post


Link to post
Share on other sites
This is a fun article that shows how to build a random number generator from a webcam and the radiation source from a smoke alarm.
link
Maybe not what you are looking for but... its cool :)

Share this post


Link to post
Share on other sites
Quote:
Original post by stevenmarky
It could be argued that everything is deterministic, so "random number generator" would be appropriate (depending on your viewpoint).


I'm out of my depth here, but I think the current idea is that we live in a probabilitistic universe(E.g. the wave function interpreted as a probability density function, or something like that. Oh yeah, and I'm contradicting the point about being deterministic, but just ignore that ok). Appparently you can get random number generators relying on some sort of external source of entrophy.

Better stop, the previous thread I saw on this topic in a different forum went for 80 pages.

Share this post


Link to post
Share on other sites
Quote:
Original post by Riviera Kid
is anything ever truly random for sure?

are the only things which are random the things we cant explain?


Gah, this is the whole point. You have to make a distinction between things which are random, and things which we can't explain, and therefore might possibly call "random", but which are deterministic.

Share this post


Link to post
Share on other sites
Reality at the quantum level is not deterministic. That by no means implies that we cannot explain or understand it — we just have to switch to probabilistic analysis. Quantum electrodynamics, the quantum theory of electromagnetism, is *the* most accurate one of all scientific theories, its predictions matching experimental data to the tenth decimal and beyond.

Share this post


Link to post
Share on other sites
Quote:
Original post by Sharlin
Reality at the quantum level is not deterministic. That by no means implies that we cannot explain or understand it — we just have to switch to probabilistic analysis. Quantum electrodynamics, the quantum theory of electromagnetism, is *the* most accurate one of all scientific theories, its predictions matching experimental data to the tenth decimal and beyond.


Quantum theory is based on the assumption that the universe is completly deterministic and given the momentem and position of a particle (as well as the forces acting on it) its exact position and momentum can be predicted at any point in time, past or future. BUT it is impossible to mesure the EXACT postion and mementum of a partice, the more accuratly one is measured the less accurate the measure of the other will be. Hence it attempts to make the best prediction it can given that there are these errors in the measurments.

Share this post


Link to post
Share on other sites
Actually some modern systems do have a true random number generator in hardware. Even if your system doesn't have such a thing, some operating systems (e.g. Linux, BSD) provide an interface which harvests random data from sources of entropy available to it (e.g. timings of unpredictable things such as user input).

In the case of a true random number generator, it should be able to generate truly random data at a prodigious rate (many megabytes per second).

In the case of operating-system dependent stuff, the amount of randomness available depends on how the system is used.

Mark

Share this post


Link to post
Share on other sites
Quote:
Original post by Julian90
Quantum theory is based on the assumption that the universe is completly deterministic and given the momentem and position of a particle (as well as the forces acting on it) its exact position and momentum can be predicted at any point in time, past or future.


No; even if you somehow got the complete quantum state of an electron at a given time (which is impossible, as you said), you still cannot predict its momentum after some delta-t because at any moment, it might spontaneously emit a photon and change its momentum unpredictably. The combined momentum of the electron-photon system is of course conserved, but you cannot know how the momentum is distributed between the two (or more).

What you *can* do is take the Feynman path integral over *all* the possible future quantum states of the electron, which will give you a probability distribution of those states. That is, the integral will tell you what the electron's most *likely* to do after some delta-t.

Share this post


Link to post
Share on other sites
Quote:
Original post by Peter Conn
Also if anyone could explain to me a bit more indepth about computers pseudorandom numbers I'd be very grateful.


I could help a bit (my bona fides: I've implemented tr1::random).

"True" random numbers are usually generated by measuring unpredictable natural phenomena: the radioactive decay of unstable isotopes, the fluctuating voltage levels across an open collector on a transistor.

Computers generate what are sometimes called pseudorandom numbers. They're "pseudo," because if you know the algorithm used, the generator's parameters, and the initial seed, you can predict every number in the sequence.

There are a large number of different algorithms used to generate pseudorandom numbers on a computer, each with different tradeoffs (the time-space tradeoff, the length of the generated sequence before it starts over, and so forth).

The most common algorithm used is the linear congruential (LCG) algorithm, which is expressed by the equation r = (ar +c) mod m. You need to choose a and m to be mutually prime to get a good distribution, and m is usually chosen to be two to the wordsize of the computer to take advantage of unsigned integer truncation for speed. Linear congruential is fast (generally two multiplictions and an addition is all it takes) and takes only one word of storage but produces a relatively short sequence of random numbers with poor spectral qualities (try plotting consecutive pairs of generated numbers on an X-Y plane: you'll see two parallel lines appear). Each number in this sequence depends on the preceding number, so as soon as a number reappears in the sequence, the sequence starts again from that point.

Another good algorithm in use is the lagged Fibonacci algorithm. Also known as subtract-with-borrow or add-with-carry, this mechanism produces much longer sequences with better spectral spread than the LCG at the cost of a much larger memory footprint (usually several words of memory). Again, the parameters need to be carefully chosen to produce good results, and studies have show that the spread can be very poor under some circumstances. What's usually done wit hthese generators is to feed the output through a filter that will effectively skip several numbers in the sequence in a row (a discard-block filter). Alternatively, two generators can be combined using something like an xor filter to produce better results than either generator alone.

Each number in a lagged Fibonacci sequence depends on two of the preceding numbers (not necessarily the immediately preceeding number, either), so the sequence does not end as soon as a number reappears. It would take both numbers reappearing in the same order to restart the sequence.

Finally, the Mersenne Twister is in vogue. It produces a very long sequence of random numbers with execllent spectral qualities at the expense of considerable memory and computation -- it's a pretty hairy algorithm involving a lot of bit shifting and dark and unspeakable magic. Each number depends on the state of the 19937 previous bits in the sequence so the sequence is very long indeed.

There are other generator functions available.

Anyways, all pseudorandom numbers are really just long sequences of numbers generated through some generating function.

Share this post


Link to post
Share on other sites
There are no random numbers, neither computers or humans can produce them.
Computers generate pseudo random numbers based on a seed and those number sequences are deterministic (not random at all) for each seed number.

God doesn't play dice ;).

Share this post


Link to post
Share on other sites
If someone could shrink down a woman small enough to be integrated to a computer's PCI interface, then we could harness their randomness in order to create true random numbers.

Share this post


Link to post
Share on other sites
Quote:
"True" random numbers are usually generated by measuring unpredictable natural phenomena: the radioactive decay of unstable isotopes, the fluctuating voltage levels across an open collector on a transistor.

Of course it is very likely that this is also deterministic, we just don't have a strong enough understanding of how it works yet. [grin]

Share this post


Link to post
Share on other sites
If there's one post worth reading in this thread, it's Bregma's. Everything you need to know about PRNGs is in there, with one possible exception:

If you're considering writing your own random number generator for anything other than personal entertainment, don't. In fact, don't even think about thinking about it. PRN generation is a siren. Programmers are lured in with the hopes of producing something wonderful, and they inevitably open Pandora's box. Generating uniformly-distributed, non-periodic pseudo-random numbers is far more complicated than you ever imagined. And way too many statistical experiments have been ruined through use of a bad PRNG.

Regards
Admiral

Share this post


Link to post
Share on other sites
Quote:
Original post by Sharlin
Quote:
Original post by Julian90
Quantum theory is based on the assumption that the universe is completly deterministic and given the momentem and position of a particle (as well as the forces acting on it) its exact position and momentum can be predicted at any point in time, past or future.


No; even if you somehow got the complete quantum state of an electron at a given time (which is impossible, as you said), you still cannot predict its momentum after some delta-t because at any moment, it might spontaneously emit a photon and change its momentum unpredictably. The combined momentum of the electron-photon system is of course conserved, but you cannot know how the momentum is distributed between the two (or more).


ofcourse then I could argue that this just implies there are observables of the system that we dont know of yet (such as the spin of a partice before the 1800's (I think, not sure on the date)) which if known would allow the change in momentem due to the emission of the photon and the exact time at which the photon is emited to be calculated and then you could go on to provide another counter example and I could go on to make the same argument and so on and so forth.

Share this post


Link to post
Share on other sites
Quote:
Original post by Julian90
ofcourse then I could argue that this just implies there are observables of the system that we dont know of yet (such as the spin of a partice before the 1800's (I think, not sure on the date)) which if known would allow the change in momentem due to the emission of the photon and the exact time at which the photon is emited to be calculated and then you could go on to provide another counter example and I could go on to make the same argument and so on and so forth.


The problem is that the statistical predictions for "a process with an observable we don't know about (i.e. hidden variable)" and for "a process that is truly random" are different, and the latter matches better with experiment.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this