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.