Random Number Generator Algorithm

Random Number Generator: 

Hello Friends,


So what are random numbers ?
Anyone will answer this question as "Random numbers are numbers which are generated randomly".
My way of answering this Q is "Numbers which are generated in such a way that does not have any pattern are called Random numbers"

We have seen in many applications where random number generator algorithm is used such as in gaming application, cryptography, etc. For example, shuffling of playing cards, dice, etc. There are built-in functions in any language to generate random numbers, but do we really know how does random function works?

Whatever values we generate in computational science are mostly Pseudo Random Numbers, which are generated by deterministic procedure. To generate True Random Number we need to use some kind of physical phenomenon like radioactive decay, thermal noise, etc.

Some of the Pseudo Random Number Generators are :

• Linear Congruential Generator
• Blum Blum Shub
• Multiple With Carry
• Inverse Congruential Generator
• Lagged Fibonacci Generator

As we generate Pseudo Random Numbers using some deterministic procedure which in turn depends on fixed number called seed (Random Seed) which is used to initialize the Pseudo Random Number Generator. The most common type of Pseudo Random Number Generator is Linear Congruential Generator whose recurrence relation is:

where X_n is the sequence of pseudo random values, and

           m, 0 <    m        — the "modulus"
           a,  0 <    a < m  — the "multiplier"
           b,  0 <=  b < m — the "incrementer"

— the "seed" or "start value"

are integer constants that specify the generator.
The pattern (period) at which same numbers can be repeatable is at most "m". Linear Congruential Generator have full period for all seed values iff (where c is non zero) :

1. b and m are relatively prime,
2. a - 1 is divisible by all prime factors of m,
3. a - 1 is a multiple of 4 if m is a multiple of 4

One of the simple way to understand what Pseudo Random Generator's are by using example described by John Von Neumann is middle-square method. This method describes as if we want to generate 6-digit random number, let it be 675248 (which is seed) and take square of that number which will be 12-digit number (if square of the number is less than double the digits of original number then leading digits are added to compensate ). Then random number for the given seed will be middle 6-digit number (which will also acts as the seed value for the next random number)




 The drawback with the above approach is that if we got the random number as all zero's , then next all generated random numbers are going to be always zero. For example, if we got the current random number as 0000, then the next random numbers are always 0000 only. For a generator of n-digit numbers, the period can be no longer than 8<sup>n


Hope you have understood the concept of random number generator. Comments are appreciated on this topic</sup>