next up previous

6 Lagged Fibonacci Generators     continued...

The problem just demonstrated is not difficult to fix. We simply need a different way of ``numbering'' the patterns in the area of the free bits in the canonical form, one that randomizes these patterns to some extent. An LCG can be used to initialize the free bits, if one is careful to use it in such a way that a unique bit pattern results for each distinct cycle number number. Pryor et al. [52] describe the use of the LCG of Park and Miller [47] as a good method for initializing their family of Fibonacci generators. In that family, M is equal to 32, so that the free bit rectangle is 31 bits high; whereas the Park and Miller generator uses a modulus of the prime number . Thus the successive values in the 31 high bits of the initial state for word 0 through word are simply the LCG successors of n. This gives a simple way to initialize distinct cycles that start out with a satisfactory ``look and feel.'' As an aside, this particular LCG passes the `bitwise'' randomness tests described by Altman [1], for use in initializing Fibonacci generators.

The second caveat related to the use of this canonical form is also highlighted by the previous example. The astute reader may have noticed that with this method of initializing the Fibonacci register, for every advance, the least significant bit is the same for all generators. Unfortunately, this is the tradeoff vs. efficiency that was made in order to guarantee uniqueness of the cycles: the least significant bit is simply non-random relative to the other cycles. For all other bit fields, including the next-to-least significant, there is no such defect. Several possibilities arise for remedying this situation, including the use of a separate, independent generator for only the least significant bit. However, in the interest of simplicity and speed, Pryor et al. have chosen to shift off the least significant bit of the generated random number, so that the numbers returned by the generator are in the range rather than . The register is initialized and maintained as a 32-bit generator, so that no loss of period length or uniqueness of cycle is incurred. And for 32-bit machines, the returned results still include all positive integers.

Figure 12: Vectorized Stepping of LFG(10,7,M).