Lagged Fibonacci Generator - Properties of Lagged Fibonacci Generators

Properties of Lagged Fibonacci Generators

Lagged Fibonacci generators have a maximum period of (2k - 1)*2M-1 if addition or subtraction is used, and (2k-1)*k if exclusive-or operations are used to combine the previous values. If, on the other hand, multiplication is used, the maximum period is (2k - 1)*2M-3, or 1/4 of period of the additive case.

For the generator to achieve this maximum period, the polynomial:

y = xk + xj + 1

must be primitive over the integers mod 2. Values of j and k satisfying this constraint have been published in the literature. Popular pairs are:

{j = 7, k = 10}, {j = 5, k = 17}, {j = 24, k = 55}, {j = 65, k = 71}, {j = 128, k = 159}, {j = 6, k = 31}, {j = 31, k = 63}, {j = 97, k = 127}, {j = 353, k = 521}, {j = 168, k = 521}, {j = 334, k = 607}, {j = 273, k = 607}, {j = 418, k = 1279}

Another list of possible values for j and k is on page 29 of volume 2 of The Art of Computer Programming:

(24,55), (38,89), (37,100), (30,127), (83,258), (107,378), (273,607), (1029,2281), (576,3217), (4187,9689), (7083,19937), (9739,23209)

Note that the smaller number have short periods (only a few "random" numbers are generated before the first "random" number is repeated and the sequence restarts).

It is required that at least one of the first k values chosen to initialise the generator be odd.

It has been suggested that good ratios between j and k are approximately the golden ratio.