Inversive congruential generator

An inverse congruential generator is an arithmetic random number generator, which avoids known drawbacks of linear congruential generators by the set of Marsaglia. In particular, it does not create hyperplanes. If one uses random numbers inverse congruence for the Box-Muller method, a spiral behavior is avoided. In return, he demands a higher computational effort.

  • 2.1 period length

General

It consists of the following components:

  • Module ( here stands as usual for the set of primes )
  • Factor
  • Increment
  • Starting value

The generator works on the following Education Act:

For explanation of the symbols see the article modulo.

Because there is a unique multiplicative inverse for each element, so that. Only one must still worry. Formally would be the inverse element of. Since it is not represented, it is best skipped by setting, as the (co ) also corresponds to the second representation.

Period length

The maximum period length can not exceed apparently. This is achieved on if and only if the polynomial

A primitive polynomial in is.

Hyperplane behavior

In contrast to linear congruential generators whose values ​​are yes to a few hyperplanes, one can show here that:

Inverse generators with composite module

In order to replace the modulo division by truncation of the most significant bit, it would be convenient, for the calculation rule modules

Allowing that are not prime, but a power of 2. These must be odd, and must be set so that all are odd, because then the inverse element can be calculated unambiguously. The period length is at most. If the following conditions are met, it is exactly:

Explicit inverse generators

Sometimes one also reads the definition

Or

The latter does not represent a generalization; obtained by multiplying the above figure immediately.

Period length

The maximum period length is again reached and, if applicable.

415536
de