Page 3 of 3
The Congruential Generator
So what method do we use that satisfies the conditions?
The answer in nearly all cases today is the “congruential random number generator”, CRNG.
All that happens is that you pick a starting value – the seed – and a number to use as the generator.
To get the next random value you multiply the seed by the generator and take the answer mod “a large value”.
Mod is a function that simply rolls over at a given value. For example 7 Mod 6 is 1 because we roll over to 0 at 6.
In the case of a general CRNG the calculation is,
a(i+1)=K*a(i) MOD P
where K is the generator and a(i+1) is the next random number. P is usually chosen to be a large power of 2 to make the arithmetic easy and K is picked, using some basic requirements and hand tuning to give a good pseudo random sequence.
The resulting value is suitably pseudo random as long as K is well chosen and it is difficult to predict the next value given any number of earlier values. In fact given a small sample of the output of a CRNG it is possible, by solving some linear equations, to work out the generator, and hence predict the entire sequence but for most purposes this doesn’t matter. In a security application it most certainly matters but if you are just using the random numbers for simulation or for games then the fact that a complex mathematical procedure can be used to predict the next number isn't relevant.
Functions for random numbers
This is the method used by nearly all programming languages. For example, most languages provide something like a rnd() function which returns a random number, a decimal fraction, in the range 0 to less than 1.
In practice the rnd function generally uses a CRNG to generate integers which it then divides down to give the decimal fraction. Each time you use rnd() the current random value is used in the CRNG to generate the next.
One interesting and useful extra is that there is usually something like randomize(Seed) which can be used to set the initial starting value or seed for the CRNG.
You can use this to generate a repeatable set of random numbers when a game or simulation is being tested because after setting the seed you always get the same sequence of values – a fact which makes many people give up on the entire concept of “random” numbers!
This repeatability may be useful in some situations but by default the rnd function often always starts from the same seed. What this means is that when you start a card game you will always be dealt the same hand!
Clearly this isn’t good and the solution takes us back to the first method suggested for generating random numbers – the timer. There is usually a command which will use some physical value that is unpredictable to seed the generator - usually the current value of the system timer, i.e. the time since the machine was switched on. This usually results in a new sequence of numbers being produced that look as if the deck has been well and truly shuffled.
If you keep in mind that pseudo random numbers are mostly about not being predictable rather than worrying about any deep philosophy of what randomness is then it all becomes much simpler.
One parting thought - if you understand the idea of a pseudo random number then don't be fooled into thinking that creating a random number generator is easy. Even if you think you have found an external source of entropy that you can use you need to know that most such ideas don't work. You need to test the numbers to confirm that they are statistically random.
Creating a good random number generator is difficult.
And finally back to that cartoon.
Can one number be random?
The simplest answer is that random is a term that really only applies to a sequence of numbers - a single number is just a number.
The Monte Carlo method
How not to shuffle - the Knuth Fisher-Yates algorithm
The Programmer's Guide to Chaos
ERNIE - A Random Number Generator