The Fibonacci sequence may be described by the recurrence relation:
Generators of this type employ k words of state (they 'remember' the last k values).
If the operation used is addition, then the generator is described as an Additive Lagged Fibonacci Generator or ALFG, if multiplication is used, it is a Multiplicative Lagged Fibonacci Generator or MLFG, and if the XOR operation is used, it is called a Two-tap Generalised Shift Feedback Register or GFSR. The Mersenne twister algorithm is a variation on a GFSR.
Lagged Fibonacci generators have a maximum period of (2k - 1)*2M-1 if addition or 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:
The initialisation of LFGs is a very complex problem; any maximum period LFG has a large number of possible cycles, all different. Choosing a cycle is possible, but methods for doing this may endanger the randomness of subsequent outputs. Secondly, 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. These reasons, combined with the existence of the free and very high-quality Mersenne twister algorithm tend to make 'home-brewed' implementations of LFGs less than desirable in the presence of superior alternatives.
see also Linear congruential generator, Mersenne twister, FISH, Pike, VIC cipherProperties of Lagged Fibonacci Generators
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:
It is required that at least one of the first k values chosen to initialise the generator be odd.
Problems with LFGs