random numbers

[toughwimp11]

not sure if this is the right forum but...

how does a computer generate random numbers. i know that it cant just generate truly random numbers because that would just be impossible as a computer is incapable of pulling something out of thin air. i also noticed this is true of two calculators that are turned on at the same time for the first time. they will give the same random numbers. anyone know how it works?

 

[Paperdoc]

A "random number generator" is actually a pre-programmed function that starts with some not-quite-random number from somewhere, then carries out some mathematical operations on it that involve irrational numbers. Those are the ones with infinitely long, non-repeating decimal values. Then it uses that no-repeating sequence to pick out a piece and hand it to you.

I had a programmable calculator years ago without such a function, but the manual suggested this:
Take in any input number from the keyboard, add pi (you know, the irrational value 3.1415926....), raise the sum to the fifth power, cut off the digits before the decimal point and return the stuff after the "0." The result is pseudo-random, and can range from 0 to 1 (well, never exactly 0 or 1). I used to save the answer, then use it as the seed for the next call to the function.

In some systems or application software, the random number function offers you a choice: you can specify the "seed" value it starts with, but you'll always get the same result if you use the same seed. Or, you can let it pick up the current time from the system clock and use that for a seed - you're not likely to stumble across the same time easily, because it is down to the nearest millisecond.

 

[Modelworks]

One way it can be done on embedded processors, like those in calculators is to have the clock crystal tied in with an analog to digital port on the cpu.

When the processor needs a random number it samples the A to D port and gets a value that is based on the voltage coming into the port at that microsecond . That value is then factored in to an equation to produce the random number.
With a 10Mhz clock your going to see that voltage changing 10 million times a second, so its a very random number.

 

[Born2bwire]

Originally posted by: Modelworks
One way it can be done on embedded processors, like those in calculators is to have the clock crystal tied in with an analog to digital port on the cpu.

When the processor needs a random number it samples the A to D port and gets a value that is based on the voltage coming into the port at that microsecond . That value is then factored in to an equation to produce the random number.
With a 10Mhz clock your going to see that voltage changing 10 million times a second, so its a very random number.

I have also heard that some processors sample other random noise like shot noise to get their seed too. Interestingly enough, pi is a considered a random number so I have always wondered if it could be used in part for a random number generator like in Paperdoc's case.

 

[f95toli]

I doubt pi is a very good random number, but I must admitt I have never seen it tested.
The problem is that good numbers are hard to find and it is rarely the "unpredictibility" which is the problem ; in e.g. Monte Carlo simulations it is important that the distribution is as "white" as possible which is why you see RNGs coming with recommended seeds: some seeds are better than others. Hence, it usually make sense to simply use the same series of number over and over again.
In the old days you could buy books which contained long tables of random numbers which were guaranteed to be good.

 

[CycloWizard]

Some programs will let you pick from a "truly random" number and a normally distributed random number. MATLAB does this, but the code that they use is in the "builtin" function, so the code is inaccessible.

 

[Markbnj]

I think the whole concept of randomness is nearly philosophical, and we may not know whether anything is truly random. Barrel shifters and other algorithmic approximations just provide a set of numbers that are a close simulacrum of randomness, in that any given number in the range has close to the same chance of appearing in the sequence as any other. Efforts at retrieving "true" random numbers that I have seen all involve some external physical property that is sampled by the system.

 

[Born2bwire]

Originally posted by: f95toli
I doubt pi is a very good random number, but I must admitt I have never seen it tested.
The problem is that good numbers are hard to find and it is rarely the "unpredictibility" which is the problem ; in e.g. Monte Carlo simulations it is important that the distribution is as "white" as possible which is why you see RNGs coming with recommended seeds: some seeds are better than others. Hence, it usually make sense to simply use the same series of number over and over again.
In the old days you could buy books which contained long tables of random numbers which were guaranteed to be good.

What I mean as a random number is that if you randomly choose any of its digits, the odds are the same that it is 0, 1, 2, ..., 9. It was used as an example for one of my Stat classes, I've long forgotten the explanation or its context but thought it interesting enough to remember.

 

[NanoStuff]

It is true that no finite state machine, including the brain can generate true random numbers. For all practical purposes that I can think of with the exception of security, pseudo-randomness is random enough. There are however online generators that will generate a true random number for you failing you have the quantum equipment to do it yourself.

 

[Nathelion]

Umm well what matters is that whoever is trying to break your code doesn't know how you came up with the "random" number. Essentially, even if the "random" number is predictable, it is enough that it is not currently possible to predict it for it to be good.
I've heard that lava-lamps are somehow used to obtain seed numbers. Don't ask me how it works though.

 

[darthsidious]

Originally posted by: Born2bwire

Originally posted by: f95toli
I doubt pi is a very good random number, but I must admitt I have never seen it tested.
The problem is that good numbers are hard to find and it is rarely the "unpredictibility" which is the problem ; in e.g. Monte Carlo simulations it is important that the distribution is as "white" as possible which is why you see RNGs coming with recommended seeds: some seeds are better than others. Hence, it usually make sense to simply use the same series of number over and over again.
In the old days you could buy books which contained long tables of random numbers which were guaranteed to be good.

What I mean as a random number is that if you randomly choose any of its digits, the odds are the same that it is 0, 1, 2, ..., 9. It was used as an example for one of my Stat classes, I've long forgotten the explanation or its context but thought it interesting enough to remember.

That isn't enough for a sequence to be random. Suppose I had the infinite sequence 01234567890123456789....... Now, if you pick a random digit, the probability of it being 0,1,2,...,9 is exactly 0.1 . But clearly, this sequence is non-random (infact, if I know the previous digit, that is enough for me to predict all future values. Therefore, I think a better definition would be that P(A| all prior elements in the sequence) = P(A), where A denotes the probability that the n th element of the sequence is some member of the possible sample space, x_i , and this is true for all n, and all members of that sample space. But maybe there is something wrong with this definition too - I essentially made it up, and I don't have much background in probability theory.

 

[imported_bearfx]

Their are some interesting ways to generate random numbers ( http://inventgeek.com/Projects/alpharad/overview.aspx comes to mind ).

If you are really interested in random number generation, I would recommend that you pick up a few books on cryptography, and make sure your math skills are up-to-date. You might also check out Bruce Schneider's page at http://www.schneier.com/ . If you are really brave, you can download an open source cryptography program and dissect it's PRNG.

As to your questions, the way it works will vary based on the implementation by the vendor. Their are good PRNG's and bad PRNG's, though most of the ones released today are pretty good.

Most will start with some sort of seed value. This value is often "gathered entropy", or randomness from some source. Some will use mouse movements, or keypresses to generate entropy, other will use static from the LINE-IN port, or from a video or radio receiver ( like random.org does). If you really want random, you can use natural phenomena, such as atomic decay or any number of values from quantum mechanics. The link at the beginning of this post points to a project using atomic decay and a ccd webcam. Depending on the algorithm, more than one source may be used.

This seed value is fed into some algorithm. http://en.wikipedia.org/wiki/Random_number_generation]Wikipedia[/url] has a few examples of algorithms. The algorithms used range from fairly simple (you can do it with pencil and paper) to mind-numbingly complex (you better buy paper by the case). As with all things, some are better than others. Their are a number of algorithms where certain numbers simply don't come up as often as they should (particularly at the very beginning and very end of the range). Weaknesses in the PRNG algorithm can be exploited, but most are actually pretty good. The major security products I have looked at have great implementations of PRNGs.

Once the algorithm calculates a number, it is put into the range requested. This is simple math, but from a programmers perspective, you should understand the function you are using (ie RND(10) may give a number greater than or equal to 0 but always less than 10).

Thus you have a pseudo-random number.

How good of a pseudo-random number you need depends on your application.

 

[Throckmorton]

Is there any such thing as randomness? When you roll a die, the result isn't random. It depends on the forces acting on the cube.

 

[darthsidious]

Originally posted by: Throckmorton
Is there any such thing as randomness? When you roll a die, the result isn't random. It depends on the forces acting on the cube.

Some quantum mechanical phenomenon are truly random - for example the decay of radioactive material

 

[Born2bwire]

Originally posted by: darthsidious

Originally posted by: Born2bwire

Originally posted by: f95toli
I doubt pi is a very good random number, but I must admitt I have never seen it tested.
The problem is that good numbers are hard to find and it is rarely the "unpredictibility" which is the problem ; in e.g. Monte Carlo simulations it is important that the distribution is as "white" as possible which is why you see RNGs coming with recommended seeds: some seeds are better than others. Hence, it usually make sense to simply use the same series of number over and over again.
In the old days you could buy books which contained long tables of random numbers which were guaranteed to be good.

What I mean as a random number is that if you randomly choose any of its digits, the odds are the same that it is 0, 1, 2, ..., 9. It was used as an example for one of my Stat classes, I've long forgotten the explanation or its context but thought it interesting enough to remember.

That isn't enough for a sequence to be random. Suppose I had the infinite sequence 01234567890123456789....... Now, if you pick a random digit, the probability of it being 0,1,2,...,9 is exactly 0.1 . But clearly, this sequence is non-random (infact, if I know the previous digit, that is enough for me to predict all future values. Therefore, I think a better definition would be that P(A| all prior elements in the sequence) = P(A), where A denotes the probability that the n th element of the sequence is some member of the possible sample space, x_i , and this is true for all n, and all members of that sample space. But maybe there is something wrong with this definition too - I essentially made it up, and I don't have much background in probability theory.

True, but in this case, pi is not a determinable sequence.

 

[Special K]

I read a paper a few months ago about a random number generator created in hardware using cross-coupled inverters. Basically, you put the pair of inverters into the metastable state, and then wait for one of the circuit nodes to settle to either 0 or 1 (which would bring the other node to the opposite value). Apparently the electrical noise that eventually disturbs the cross-coupled inverters from their metastable state is random enough to be considered a "true" random number generator, at least according to the paper's authors.

 

[hellokeith]

Originally posted by: Markbnj
I think the whole concept of randomness is nearly philosophical, and we may not know whether anything is truly random.

Wholeheartedly agree.

Randomness highly depends on your definition and scope. If you have a billion element sequence, but only sampled the ten consecutive 4's somewhere in the middle of the sequence, you would likely conclude the sequence is not random, or not "random enough" which gets into repetitions and patterns and how are they accounted for within a random number distribution.

I think the typical definition of random is a non-repeating number sequence, which is pretty easy to achieve since you just store the last generated value (or last X number of values) and either wait for a non-repeating value or use the stored value(s) to ensure non-repitition. Just for clarification, I am not saying I think a non-repeating number sequence is the correct definition of randomness, because it is obvious in real-world analog incidents that repetitions and even patterns can occur without negating impredictability.