Inverse congruence generator

from Wikipedia, the free encyclopedia

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).