Additive Congruential Method : maths and logic behind its spread
Additive Congruential Method is yet another method to generate random number in software systems which can be very easily implemented at the hardware level too.
The idea is to start with a register filled with some arbitrary pattern, then shift it right (say) a step at a time, filling in vacated positions from the left with a bit determined by the contents of the register. The diagram below shows a simple 4-bit register, with the new bit taken as the “exclusive or” of the two rightmost bits.
So, if there are 4 bits b1, b2, b3, b4 and b1-b2-b3-b4 is any random number generated; then the next number which will be generated will be such that b4(new) = b3, b3(new) = b2, b2(new) = b1 and b1(new) = b3XORb4.
The above example is for 4 bits and the algorithm is replicated for n bits too.
The problem in hand is to observe if any random number picked as seed will span all the possible numbers or not. I found a pretty elegant solution for the problem. Taking seed as 0000 clearly shows that cycle for such random number generator will be 1 as next operation on 0000 will lead us to 0000 itself. Lets see what happens when we take 1111 as seed. The cycle is as shown for the taken seed:
1111->0111->0011->0001->1000->0100->0010->1001->1100->0110->1011->0101->1010->1101->1110->1111
Clearly cycle spans complete range except 0000.
Now it becomes obvious that any seed taken can be either 0000 or one number among the cycle mentioned above. If seed taken is 0000, cycle is of size 1 and hence it should be a must check that seed is not 0. Read the rest of this entry »
