Appendix: Linear Recurrences

In the present section we recall the basic recurrences behind linear generation methods. We use a simplified presentation without discussing special implementation techniques, in order to demonstrate cross connections between the different methods. The exact definitions, implementation features and conditions on the parameters of each generation method are given in the excellent surveys [134,141,183,186].

For the following subsections, let be a prime number and let , , be certain parameters. We limit our representations to the prime case since (i) this is the most important case for recent implementations, (ii) it provides fundamental theoretical support to derive the basic properties of the recurrences (since can be identified with the finite field of order ), and (iii) it yields a unified framework for linear generation methods.

(Multiplicative) Linear Congruential Generator

As can be seen from Section ,
the *linear congruential generator* (LCG)
is the workhorse of random number generation and, surprisingly,
even for parallel Monte Carlo.

We recall the basic recurrence behind multiplicative LCGs, which is

For primitive elements modulo this recurrence yields a period . Uniform random numbers in are obtained by the transformation . For LCGs there exists a more general form of the recurrence above: , prime or . The case is considered less relevant because of the regularities in the binary representations of the generated numbers [126, p. 12] which are also responsible for the quality of lagged subsequences with large power-of-two step sizes (compare Section ). Nevertheless the latter version is still widely available, see Section .

Directly equivalent or essentially equivalent to large LCGs are combined LCGs [235,149] and add-with-carry - or subtract-with-borrow generators [167,224,222].

Multiple Recursive Generator

A generalized form of a linear generator,
the *multiple recursive generator* (MRG), is based on the higher
order recurrence (see Section for examples):

MRGs yield larger periods (, if the characteristic polynomial of the latter recurrence is a primitive polynomial over ), better structural properties than simple LCGs with the same modulus, and implementations as fast and easy as LCGs (if implemented in the form ), for details see [142,144,183]. For structural deficiencies of the latter implementation form see [115].

Equivalent or approximately equivalent to (large) MRGs are combined MRGs [135], additive lagged Fibonacci generators, or the widely available combined generator RANMAR (see [107,34]).

Matrix Method

The analog to the multiplicative LCG in matrix form
is called the *matrix method*.
Let
be a primitive polynomial and
be a matrix with elements in and with
characteristic polynomial . Consider the recurrence

The conditions above guarantee a period length of . For references and an overview of this method see [134,186].

With the matrix method we obtain two different approaches of random number generation:

- (i)
- For a large prime , the recurrence above yields random vectors .
- (ii)
- For small primes such as , we get binary -dimensional vectors, from which random numbers in may be derived.

Examples of RNGs (in their different implementation form) belonging to these classes are (i) matrix generators for random vector generation, and (ii) digital multistep sequences, Tausworthe generators, GFSR (generalized feedback shift register) generators, MRGs and lagged Fibonacci generators.

Multiple Recursive Matrix Generator

Niederreiter introduced the unified framework for ``linear'' methods,
the *multiple-recursive matrix method*,
see [186, Sect. 4.1 and 5.2] (the basic principle in
``large matrix form'' was also introduced by L`Ecuyer
[134, Sect. 3.7, 3.8]).

Consider matrices with elements in .
Then the basic recurrence for the latter method is

Quote from [186] :

Especially the twisted GFSR generator yields high performance random numbers with excellent distribution properties up to high dimensions and huge periods , see [173,174,175] and the homepage of Makoto Matsumoto.