Linear Congruential Generators

Linear Congruential Generators (LCG) are one of the oldest and most studied RNGs [8]. A LCG is parameterized by three integers $A, B$, and $M$. Its basic form is

$$x_{n+1} = (Ax_n + B) \mbox{ mod } M$$

There are two characteristics of LCGs:

• Periodicity. Given an initial seed $x_0$, there is some $n \le M$ such that $x_n=x_0$. We say the periodicity of this LCG is the least such $n$. The existence of period can be proved by a simple application of the pigeonhole principle.

• Parallel Hyperplanes (Lattices). When we plot the set of $k$-dimensional points $(x_n, x_{n+1},$ $\ldots,$ $x_{n+k-1})$ (for all $n$) in $k$-dimensional space, we will observe that all points fall mainly in the hyperplanes. There are actually more than one set of parallel hyperplanes if seeing the $k$-dimensional space from a different orientation. Figures 1 and 2 illustrate this phenomenon.

Figure 1: Two-dimensional plot of ($U_i$,$U_{i+1}$) produced by LCG. The parameters are $M=256$ and $B=2$.

Figure 2: Three-dimensional lattice structure of IBM RANDU LCG in the unit cube.

[scale=0.7]figures/randu.eps

A LCG has full period if its period length is $M$. There are several conditions for an LCG to reach full period. For example, $B$ and $M$ must be relatively prime; any prime divides $M$ must also divide $A-1$ [8]. Long period is easy to achieve but is not everything, because LCGs with $A=B=1$ is perfectly 1-distributed, but they have terrible statistical properties like extremely high autocorrelation.

Another requirement for a good LCG is to minimize the ``parallel hyperplanes'' phenomenon [6]. Let $d_{ki}$ be the distance between two parallel hyperplanes seen from orientation $i$. Then $d_k = \max(d_{k1}, d_{k2}, \ldots)$ is the $k$-dimensional maximum distance between two parallel hyperplanes from all orientations. The search for optimal parameters that minimizes $d_k$ thus becomes the most important issue for LCGs. Fortunately, one test called Spectral test is designed to quickly calculate $d_k$ given $A$, $M$, and $k$.

The generalized congruential generators have the following form (see [10]):

$$x_{n+1} = G(x_n,x_{n-1}, \ldots, x_{n-k+1}) \mbox{ mod } M$$

For example, a quadratic congruential generator has $G = A_1x_n^2+A_2x_n+C$. If linearity must be maintained, then we can take $G = A_1x_n+A_2x_{n+1} + \ldots A_kx_{n-k+1}$. This kind of generator is called multiplicative recursive generator (MRG). A restricted form of MRG called Fibonacci generator has only two of the $A_i$ coefficients being nonzero. These variants may have longer periods and good statistical properties, but it is more complicated to assess their periodicities and randomness based on their parameters.

In this project we have implemented a special kind of LCG called Prime Modulus Multiplicative Linear Congruential Generator (PMMLCG.) Its parameters are $B=0$ and $M$ being a prime. The advantage of PMMLCG is that it eliminates an addition, has an almost full period (of length $M-1$), and can be subjected to the Spectral test.