next up previous

6 Lagged Fibonacci Generators     continued...

In general, the canonical form for initializing Fibonacci generators requires that word be set to all zero bits and that the least significant bits of all words in the register to be set to zero, with the exception of one or two characteristic bits that depend on and k. As shown in Figure 11, the canonical form for the generator requires the least significant bit of word 7 to be set to one, with all other least significant bits in the register set to zero. Table 4 lists, for several choices of , the characteristic word (or words) for which the least significant bit should be set to one in order to be in canonical form.

Table 4: Canonical Form Specifications for Selected Fibonacci Generators.

Two caveats with respect to the use of this canonical form should be mentioned at this point. Suppose a user were to construct and initialize a number of generators using an initialization scheme that simply numbered the initial states as one would number the integers in a normal binary representation. This method certainly would not violate the conditions under which the canonical form produces distinct cycles, and indeed the cycles of random numbers generated from each initial state would be different. But the first few random numbers from these cycles may be less than random-looking when compared both with corresponding output from other generators and with successive values from the same generator. As an example, consider the generator, where we canonically initialize one register with all zeros in the z-ed region of Figure 11 (call this generator ``A'') and a second generator with a single one in the lower right corner of the z-ed region (call this generator ``B''). Table 5 lists the first 100 pseudo-random numbers produced by both of these generators, both as integers in the range [0,15] and as floating point numbers in the range [0.0,1.0). Note that the A sequence consists of low numbers (less than 0.5) for 43 iterations and is actually either zero or one for the first 19 iterations. B is somewhat better, but still not very satisfying. In addition, A and B appear, at least until about 50 iterations, to be correlated. This appearance of non-random behavior on the part of these two sample sequences does not mean that Fibonacci sequences or this method of initializing them does not produce high quality random numbers. ``Flat spots'' are to be expected in any good pseudo-random number sequence of sufficient length, and indeed such a sequence without them would be suspect with regard to its randomness. The problem with initializing A and B in the example is that the flat spots were ``lined up'' with each other and were placed at the very beginning. Neither of these results would be a problem if our application required the use of thousands of numbers from both the A and the B sequences and if the numbers generated at the beginning were no more important than those generated later. After a short time, the two sequences would look completely uncorrelated from each other and would appear internally random as well. However, if the number of required pseudo-random numbers is small, the outcome of the numerical experiment might be unexpectedly skewed due to the initial conditions.

Table 5a: The First 100 Random Numbers from LFGs "A" and "B" (part 1).

Table 5b: The First 100 Random Numbers from LFGs "A" and "B" (part 2). d Fibonacci Generators.