Inside Random Numbers
Written by Mike James   
Article Index
Inside Random Numbers
Software Randomness
The Congruential Generator

We often refer to things that are unpredictable as being "random" but this is not the same as truly random behavior - which is something we have to work hard to achieve. Put another way - how can a logical deterministic device like a computer produce a random number?

What Is Random?

Most things that are unpredictable in a common sense way we call “random” but it is important to notice that this isn’t the same thing as truly random behavior.

You could say that true randomness isn’t really a part of everyday life and experience.

For example, if you throw a coin up in the air you might say that which side it comes down is “random”. However, if you think a little more carefully what you are saying is that the physics of the process are simply not within your powers to predict.

You could imagine that if you measured the forces applied to the coin and knew its mass and shape then application of Newton’s laws of motion would make the outcome predictable. OK there would be problems such as air currents and so on in making the calculation but you can see that by putting enough effort into the problem, in principle if not in practice, you can reduce something that is random to something that is predictable.

This is how it nearly always is and unless you are a quantum physicist you really should think in terms of randomness as meaning “unpredictable”. Although it isn’t really important from a computing point of view most people do like to know if there is such a thing true randomness.

One answer to this question is hinted at in an earlier comment. Only quantum physics seems to provide us with examples of true randomness because part of its dogma is that quantum processes are in principle unpredictable.

If you accept the truth of quantum mechanics then the best you can do is to give probabilities for what is going to happen. When the objects involved get larger than these probabilities move closer to one and zero and we have the approximation to the world we live in where things can be certain and predictable.

A second and slightly more modern answer is that some processes are chaotic. What this means is that while they are governed by exact equations the sensitivity of the output to the inputs is such that tiny changes in the initial conditions produce extremely different outcomes. This makes a system predictable in theory but not predictable in any reasonable definition of "practical".

This last conception is closer to the computer's implementation of random but some argue that chaos is true randomness while others reserve the term for the quantum mechanical sort that is in principle not predictable.

It is worth stating again that this level of discussion is more suited to philosophy. What matters about practical randomness is that there are no patterns that make the future outcomes predictable.

Random Number

xkcd

More cartoon fun at xkcd a webcomic of romance,sarcasm, math, and language

 

Can a single number be random?

Computers and Randomness

So moving back to computers and randomness what sort of things can we make a computer do that makes it look unpredictable?

Notice that even here we have to be weaker than simply saying “to make a computer behave randomly”. The reason is that even though “random” mostly means the same as “unpredictable” there is a big difference between the unpredictability of tossing a coin and what you can make a computer do.

The difference is, of course, the program.

When you toss a coin you are giving in to vague mechanics to produce something that is unpredictable. When you program a computer everything is precisely and entirely predicable. The fact that a program makes a computer do what it does means that, unlike the coin, you always have a mechanism for predicting what it is going to do i.e. the program it is running always determines exactly what is going to happened and reading it through reveals all. In general a program given the same set of inputs or initial conditions will always produce exactly the same outputs - what could be more predictable?

For this reason the sort of unpredictability that a computer can produce is usually called “pseudo randomness” – or false randomness.

In practice the difference between true randomness, randomness, and “pseudo randomness” doesn't matter but you still have to be clear in your mind about which one you are discussing, particularly when criticizing a situation that is claimed to be “random”.

Sources of Entropy

One way of creating a random program is to make use of an input to the computer that is random. This is usually referred to as making use of a source of entropy i.e. disorder. For example, you could read an input pin connected to a device that generates a random signal and turn this into a random number. Physical random number generators of this sort are used but they are much more difficult to create than you might think. It is very easy for regularity to find its way into what you might assume is a random signal. 

Once entropy source that is guaranteed by the laws of physics to be random is the decay of a radioactive substance. You can use the output from a Geiger counter to generate random numbers of the highest quality but this isn't a practical way to do the job in most cases.

rand

One way to get real random numbers - an early random number generator used radioactive decay to generate a random signal.

 

What we need is a program that will generate unpredictable numbers without the use of an external source of entropy.

 

Banner

<ASIN:081297381X>

<ASIN:1852334177>

<ASIN:0812975219>

<ASIN:0833030477>



 
 

   
RSS feed of all content
I Programmer - full contents
Copyright © 2014 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.