Sunday, May 11, 2014

In this post we look about a pseudo random number generator algorithm but we will revert to Queue implementation shortly. Specifically we discuss Mercene Twister algorithm. This method is based on Mersenne prime number and hence its name. The prime number has a value to 2 ^ 19937 -1. This method is said to be commonly used for most of the languages. Python Ruby Pascal PHP Maple MATLAB etc.
The commonly used version of this algorithm is called MT19937 which produces a sequence of 32 bit integers/
This method has a very long period of 2 ^ 19937  - 1. With a long period, there is more distribution and though it does not guarantee randomness, there is less so shorter periods.
It is k-distributed to 32 bit accuracy for every 1 < k < 623.
A pseudo-random sequence xi of w-bit integers of period P and is said to be k-distributed to v-bit accuracy, when we take the numbers formed by the leading v bits of x then each of the possible 2 ^ kv possible combinations of bits occurs  the same number of times in a period. We can discount the all-zero combinations. Essentially we say that they are unique even if we take just a portion their bits. Random numbers are generally not expected to repeat. So using 32 bit notations all 32 bits are involved in making them distinct. But if we take only a few of the bits and they are still distinct, then they are said to be k-distributed.
Also, this method passes numerous tests for statistical randomness.

No comments:

Post a Comment