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 $p$ be a prime number and let $a, b, a_1, \ldots, a_k \in {\bf Z}_p$, $k \ge 2$, be certain parameters. We limit our representations to the prime case ${\bf Z}_p$ 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 ${\bf Z}_p$ can be identified with the finite field ${\bf F}_p$ of order $p$), 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

$$\fbox{ $ \displaystyle x_n \equiv a\cdot x_{n-1}\!\!\pmod p, \quad n\ge 0, \; x_0 \in {\bf Z}_p. $ }$$

For primitive elements $a$ modulo $p$ this recurrence yields a period $per = p-1$. Uniform random numbers in $[0,1[$ are obtained by the transformation $u_n:= x_n/p$. For LCGs there exists a more general form of the recurrence above: $x_n \equiv a\cdot x_{n-1} + b\!\!\pmod m$, $m$ prime or $m = 2^\alpha$. The case $m = 2^\alpha$ 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):

$$\fbox{ $ \displaystyle x_n \equiv a_1\cdot x_{n-1} + \ldot... ...uad n\ge 0,\; k>1, \quad x_0,\ldots,x_{k-1} \in {\bf Z}_p. $ }$$

MRGs yield larger periods ($per = p^k-1$, if the characteristic polynomial of the latter recurrence is a primitive polynomial over ${\bf Z}_p$), better structural properties than simple LCGs with the same modulus, and implementations as fast and easy as LCGs (if implemented in the form $x_n \equiv a_r\!\cdot\! x_{n-r}+a_k\!\cdot\! x_{n-k} \!\!\pmod p$), 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 $P(z) = z^d - a_1 z^{d-1} - \cdots - a_d$ be a primitive polynomial and $A$ be a $d\times d$ matrix with elements in ${\bf Z}_p$ and with characteristic polynomial $P(z)$. Consider the recurrence

$$\fbox{ $ \displaystyle X_n \equiv A\cdot X_{n-1} \!\!\pmod p, \quad n\ge 0, \; X_0 \in {\bf Z}_p^d. $ }$$

The conditions above guarantee a period length of $per = p^d-1$. 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 $p$, the recurrence above yields random vectors $X_n/p \in [0,1[^d$.

(ii)

For small primes such as $p = 2$, we get binary $d$-dimensional vectors, from which random numbers in $[0,1[$ 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 $l\times l$ matrices $A_i$ with elements in ${\bf Z}_p$. Then the basic recurrence for the latter method is

$$\fbox{ $ \displaystyle X_n \equiv A_1 X_{n-1}\mbox{\small +... ...pmod p,\quad n\ge 0, \; X_0,\ldots,X_{k-1} \in {\bf Z}_p^l $ }$$

Quote from [186] : The method includes several of the methods discussed earlier as special cases, such as the multiplicative linear congruential method (with prime modulus), the multiple-recursive congruential method (with prime modulus), the GFSR method, and the twisted GFSR generator.

Especially the twisted GFSR generator yields high performance random numbers with excellent distribution properties up to high dimensions and huge periods $per = p^{l\cdot k}-1$, see [173,174,175] and the homepage of Makoto Matsumoto.