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

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 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. Creating a good random number generator is difficult.

 

Related Articles

Mod function
 
To be informed about new articles on I Programmer, install the I Programmer Toolbar, subscribe to the RSS feed, follow us on, Twitter, Facebook, Google+ or Linkedin,  or sign up for our weekly newsletter.
 
blog comments powered by Disqus
 
Banner


What if Babbage..?

It was on this day 220 years ago (December 26 1791) that Charles Babbage was born. The calculating machines he invented in the 19th century, although  never fully  realised in his lifetime, [ ... ]



Codd and his Rules

Theories of how we should organize databases are thin on the ground. The one exception is the work of E.F. Codd, the originator of the commandment-like “Codd’s Rules”. This approach to database  [ ... ]


Other Articles


 

<ASIN:0674107462>

<ASIN:0822957558>

<ASIN:3540744169>



 
 

   
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.