next up previous

6 Lagged Fibonacci Generators     continued...

The above equation gives a way to leap the generator ahead, similar in fashion to the leap ahead concept discussed for LCGs. But such an operation with a Fibonacci generator requires a matrix-vector multiply involving, at best, the precomputation of possibly many multiples of . This precomputation may be expensive, even for small values of (recall that is ), and may be prohibitive for large values of . Leaping a Fibonacci generator ahead is therefore not recommended. This does not mean that such a generator cannot be ``split,'' however. We now look at an efficient method for splitting a Fibonacci generator.

Before explaining the splitting technique, notice that the period, P, of a properly constructed Fibonacci generator is . Consider a given initial set of values of an M-bit, -long Fibonacci register. This state is a particular bit pattern in the rectangular register. If the register is advanced P times, the initial pattern will be replaced by P - 1 different patterns before the initial one reappears. But the number of possible bit patterns in the register is , a number far larger than P. This tells us that there are many P-long cycles that are independent of one other and can be generated from the same structure. The number of such full-period cycles is [41]. For example, with the generator of our previous example, there are separate full-period cycles and a much smaller number of less than full-period cycles (, to be precise).

The question now becomes, how do we initialize separate cycles?