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:
