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.
x86 RDRAND Instruction
Newer x86 and x86-64 processors have the instruction RDRAND for generating random numbers. To use RDRAND you will first need to check if the instruction is available.
mov eax, 1 ; set EAX to request function 1
mov ecx, 0 ; set ECX to request subfunction 0
cpuid
shr ecx, 30 ; the result we want is in ECX...
and ecx, 1 ; ...test for the flag of interest...
If ECX is set to 1, the instruction is available. Then it can be used to generate a 16/32/64 bit random number (depending on the register size used as an argument).
rdrand eax ;generate a 32 bit random number and store it in EAX
Pseudorandom number generators
The Standard's Example
Taken directly from the C standard document:
// The following functions define a portable implementation of rand and srand.
static unsigned long int next = 1;
int rand( void ) // RAND_MAX assumed to be 32767
{
next = next * 1103515245 + 12345;
return (unsigned int)(next / 65536) % 32768;
}
void srand( unsigned int seed )
{
next = seed;
}
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. It is based off of the K&R C book.
int random_seed=0;
int maxrand(int seed,int max)
{
random_seed = random_seed+seed * 1103515245 +12345;
return (unsigned int)(random_seed / 65536) % (max+1);
}
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.
Linear feedback shift register
A Linear Feedback Shift Register (LFSR) is a simple way to generate a very long sequence of random numbers, given a non-zero seed. The idea is as follows: an n-bit LFSR has n 'registers', each containing one bit (either 0 or 1). Initially, all the registers are filled with the bits from an n-bit seed. For each next value to be generated, take some bits from certain registers and XOR them together. Feed the resulting binary value into the left-most register, shifting all bits one position to the right. The bit that is shifted out of the LFSR on the right-most side is the generated random bit.
The sequence of bits that an LFSR can produce will eventually repeat, but by choosing the XOR'ed bits carefully the period of the LFSR can be increased to up to 2n - 1 bits. This means that after a sequence of 2n - 1 bits, the same sequence will be returned. However, this is a property that all pseudo-random number generators have: without changing the seed, they will eventually repeat themselves.
The following is an example of an 16-bit LFSR using bits 11, 13, 14 and 16 XOR'ed together as its input. The period of this LFSR is 65535 bits, so it will generate a pseudo-random sequence of 65535 bits before the sequence repeats itself. The next bit produced by the LFSR is 1 (the value of bit 16) and the next input bit is 0.
1 11 13 14 16
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
INPUT --> | 0 1 0 0 0 1 0 0 1 1 1 1 0 0 0 1 | --> OUTPUT
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
INPUT = bit 11 XOR bit 13 XOR bit 14 XOR bit 16
Larger (and smaller) LFSR's are also possible. Smart people have derived polynomials that will ensure that given any non-zero input, the period of the LFSR is as large as it can be (2n - 1). Such a polynomial are written as x16 + x14 + x13 + x11 + 1. For this example polynomial for n = 16, bits 16, 14, 13 and 11 must be XOR'ed together and provided as input, counting from the left and starting with 1. Polynomials for other values of n can be found here on Wikipedia and on page 5 of this PDF document.
Note that the seed must never be zero. This also means that it is never possible for all registers to have bit value zero, and that of the 2n possible combinations of registers, the all-zero state is not allowed. Therefore, 2n - 1 states is the maximum possible.