next up previous

6 Lagged Fibonacci Generators     continued...

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).