Lagged Fibonacci generator

Lagged Fibonacci generators have a maximum period of (2^k − 1)*2^M-1 if addition or subtraction is used, and (2^k − 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 (2^k − 1) × 2^M−3, or 1/4 of period of the additive case.

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

y = x^k + x^j + 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).

If addition is used, it is required that at least one of the first k values chosen to initialise the generator be odd; if multiplication is used, instead, it is required that all the first k values be odd.[1]

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

In a paper on four-tap shift registers, Robert M. Ziff, referring to LFGs that use the XOR operator, states that "It is now widely known that such generators, in particular with the two-tap rules such as R(103, 250), have serious deficiencies. Marsaglia observed very poor behavior with R(24, 55) and smaller generators, and advised against using generators of this type altogether. ... The basic problem of two-tap generators R(a, b) is that they have a built-in three-point correlation between ${\displaystyle x_{n}}$, ${\displaystyle x_{n-a}}$, and ${\displaystyle x_{n-b}}$, simply given by the generator itself ... While these correlations are spread over the size ${\displaystyle p=max(a,b,c,\ldots )}$ of the generator itself, they can evidently still lead to significant errors.".[3] This only refers to the standard LFG where each new number in the sequence depends on two previous numbers. A three-tap LFG has been shown to eliminate some statistical problems such as failing the Birthday Spacings and Generalized Triple tests.[2]

The initialization of LFGs is a very complex problem. The output of LFGs is very sensitive to initial conditions, and statistical defects may appear initially but also periodically in the output sequence unless extreme care is taken. Another potential problem with LFGs is that the mathematical theory behind them is incomplete, making it necessary to rely on statistical tests rather than theoretical performance.

• Freeciv uses a lagged Fibonacci generator with {j = 24, k = 55} for its random number generator.
• The Boost library includes an implementation of a lagged Fibonacci generator.
• Subtract with carry, a lagged Fibonacci generator engine, is included in the C++11 library.
• The Oracle Database implements this generator in its DBMS_RANDOM package (available in Oracle 8 and newer versions).

Wikipedia page 'List_of_random_number_generators' lists other PRNGs including some with better statistical qualitites:

• Linear congruential generator
• ACORN generator
• Mersenne Twister
• Xoroshiro128+
• FISH (cipher)
• Pike
• VIC cipher

Toward a universal random number generator, G.Marsaglia, A.Zaman