Inverse congruence generator
An inverse congruence generator is an arithmetic random number generator that avoids the disadvantages of linear congruence generators known from the Marsaglia theorem . In particular, it does not allow hyperplanes to arise. If random numbers of inverse congruence generators are used for the Box-Muller method , spiral behavior is avoided. In return, it requires more computational effort.
General
It consists of the following components:
- Module ( stands for the set of prime numbers as usual )
- factor
- Increment
- Starting value
The generator works according to the following education law:
For an explanation of the symbols, see the article Modulo .
Because there is a unique multiplicative inverse element for each , so that . Only you have to make even thoughts. In purely formal terms, the inverse element of . Since it cannot be represented, it is best to skip it by setting what also corresponds to the second representation .
Period length
The maximum period length can obviously not exceed. This is achieved exactly when the polynomial
is a primitive polynomial in .
Hyperplane behavior
In contrast to linear congruence generators , whose values are on a few hyperplanes, one can show here that the following applies:
- Each hyperplane in contains at most points of the shape
- as long as applies. Due to this condition, exactly points are eliminated. Anything can be selected.
Inverse generators with composite module
In order to be able to replace the modulo division by truncating the most significant bits, it would be convenient to use modules for the calculation rule
that are not a prime number, but a power of 2. This must be odd, and must be specified so that all are odd, because then the inverse element can be calculated too clearly. The period length is at most . If the following conditions are met, it is exactly :
Explicit inverse generators
Sometimes you read the definition too
or
The latter is not a generalization; the above figure is obtained immediately by multiplying it out.
Period length
The maximum period length is again , and is reached if applies.
literature
- Harald Niederreiter : Random Number Generation and Quasi-Monte Carlo Methods. Society for Industrial & Applied Mathematics, Philadelphia PA 1992, ISBN 0-89871-295-5 ( Regional Conference Series in Applied Mathematics 63).