Random Number Generator
Random number generators (RNG) can be implemented in lots of different ways. This article explains some of them.
Types of random number generators
There are three types of random number generators:
- True random numbers: The generated values are really random, that means, that you cannot "predict" the next number, because they don't follow any recognizable patterns. Linux provides /dev/random for this.
- pseudorandom numbers: The generated values aren't random, because they are calculated.
- hybrid: The random number generator uses both methods to calculate the random number. E.g. it uses a true random number as s initial value (often refered to as "seed") for an algorithm, that generates pseudorandom numbers. This method is the most commonly used method in OSes, since it is fast and generates very useful results. Indeed Linux does it this way to provide /dev/urandom.
True random number generators
True random number generators use physical devices to generate random numbers, whose unpredictability can be traced to the laws of quantum mechanics. Another commonly used "resource" is the behaviour of the user. Here the system generates values out of mouse movements, keyboard inputs or other human actions. Finally a very simple way to obtain a seed is getting the time value of the system's Real Time Clock.
Pseudorandom number generators
Simple Number Generator
This is a simple number generator that generates integers based on a seed and a maximum. It requires that random_seed(with a initial value) is defined.
int random_seed=0;
int rand(int seed,int max)
{
int tmpmax=max+1;
random_seed = random_seed+seed * 1103515245 +12345;
return (unsigned int)(random_seed / 65536) % tmpmax;
}
Linear congruential generator
The LCG is one of the oldest, but also one of the most simple algorithm to generate streams of pseudorandom numbers. Its based on this recurrence formula
Xn+1 = (aXn + c) mod m
where the modulus m is the number of random value the LCG produces. The quality of this algorithm highly relies on chosing the right values for a, c and m. One good assignment is
m = 232, a = 1103515245, c = 12345
as it's used in the glib. So to generate a random number, choose a seed, which is X0. Then you can calculate the next random number in the stream, i.e. X1, by calculating:
X1 = (aX0 + c) mod m
To get the next random number X2 take X1 and calculate:
X2 = (aX1 + c) mod m
and so on. Notice that this algorithm just generates m random numbers. So after m calculations it generates your seed again. Therefore it is a good idea to change the seed frequently. For more values of a,c and m, see http://en.wikipedia.org/wiki/Linear_congruential_generator#LCGs_in_common_use.
Fibonacci random number
My OS uses a special "remake" of the Fibonacci sequence to generate random numbers. This is done by having 4 "seeds", which start off as really weird values (e.g. 45, 80, 22, 32).
I implemented a seed() function which adds a new seed to the end of the sequence, and erases the first one (the seeds are referred to as A, B, C and D). The rand() function just returns the sum of the seeds, and calls seed() with the result.