next up previous

6 Lagged Fibonacci Generators

Lagged Fibonacci pseudo-random number generators have become increasingly popular in recent years. These generators are so named because of their similarity to the familiar Fibonacci sequence:

where the first two values, and , must be supplied. This formula is generalized to give a family of pseudo-random number generators of the form:

and where, instead of two initial values, initial values, , ... , , are needed in order to compute the next sequence element. In this expression the ``lags'' are k and , so that the current value of X is determined by the value of X k places ago and places ago. In addition, for most applications of interest m is a power of two. That is, . (This type of pseudo-random number generator, along with several others, has been extensively tested for randomness properties by Marsaglia [39] and has been given high marks. The only deficiency found was related to what he calls the Birthday Spacings test, for low values of and k. The interested reader is referred to Marsaglia, 1985.)

With proper choice of k, , and the first values of X, the period, P, of this generator is equal to . Proper choice of and k here means that the trinomial is primitive over the integers mod 2. The only condition on the first values is that at least one of them must be odd. Using the notation to indicate the lags and the power of two modulus, examples of two commonly used versions of these generators are: