Mother-of-All
pseudo random number generator

This is a so-called multiply-with-carry or recursion-with-carry generator, invented by George Marsaglia

Algorithm:

S = 2111111111 · X_n-4 + 1492 · X_n-3 + 1776 · X_n-2 + 5115 · X_n-1 + C

X_n = S modulo 2³²

C = floor(S / 2³²)

The last four X'es and C are stored in a buffer as 32-bit unsigned integers. The intermediate S is a 64-bit unsigned integer.

The X'es and C are initialized to random values based on a seed. They cannot all be zero.

This algorithm is most effectively implemented in assembly language where you have an instruction for multiplying two 32-bit integers and get a 64-bit product. In high level languages you do not have such an instruction, so you have to use floating point numbers with a mantissa of at least 63 bits. Not all compilers support this precision, for example Microsoft Visual C++ does not.

Specifications:

• 32-bit integer output
• cycle length is 3·10⁴⁷
• very good randomness