Obviously, the value of the modulus, **m**, does not by itself limit the period
of
the generator, as it does in the case of an LCG. Note also that lagged
Fibonacci pseudo-random number generation is computationally simple: an integer
add, a logical AND (to accomplish the mod operation), and the
decrementing
of two array pointers are the only operations required to produce a new random
number **X**. Furthermore, with a large enough value of **k**, limited
vectorization can be achieved. The major drawback in the case of this type of
generator is the fact that words of memory must be kept current. An LCG
requires only one: the last value of **X** generated.

Figure 8: State Transition Diagram for Binary Shift Register.

We now look at some of the theory of these generators, with a view toward
ensuring their proper use. Conceptually, a Fibonacci
generator acts the same as
a linear shift register, and if we set **M = 1** so that ,
then we have
a binary linear shift register. Figure 8 is a diagram of a particular binary
linear shift register, where , **k = 7**, and every is
either a 1
or a 0. (We will use this choice of and **k** in
several examples in order
to illustrate in a non-trivial way some of the properties of this type of
generator.) The arrows are there to depict the motion of the shift register as
it makes the transition from one state to the next. This is called advancing
the register. Two such advances are shown in Figure 9.

Figure 9: State Two Register Steps of LFG (10, 7, 1).