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.
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
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].
A generalized form of a linear generator,
the multiple recursive generator (MRG), is based on the higher
order recurrence (see Section for examples):
Equivalent or approximately equivalent to (large) MRGs are combined MRGs , additive lagged Fibonacci generators, or the widely available combined generator RANMAR (see [107,34]).
The analog to the multiplicative LCG in matrix form
is called the matrix method.
be a primitive polynomial and
be a matrix with elements in and with
characteristic polynomial . Consider the recurrence
With the matrix method we obtain two different approaches of random number generation:
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.
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
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.