Lagged Fibonacci Generator
A Lagged Fibonacci generator (LFG) is an example of a pseudorandom number generator. This class of random number generator is aimed at being an improvement on the 'standard' linear congruential generator. These are based on a generalisation of the Fibonacci sequence.
The Fibonacci sequence may be described by the recurrence relation:
Hence, the new term is the sum of the last two terms in the sequence. This can be generalised to the sequence:
In which case, the new term is some combination of any two previous terms. m is usually a power of 2 (m = 2M), often 232 or 264. The operator denotes a general binary operation. This may be either addition, subtraction, multiplication, or the bitwise arithmetic exclusive-or operator (XOR). The theory of this type of generator is rather complex, and it may not be sufficient simply to choose random values for j and k. These generators also tend to be very sensitive to initialisation.
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 feedback shift register or GFSR. The Mersenne twister algorithm is a variation on a GFSR. The GFSR is also related to the Linear Feedback Shift Register, or LFSR.
Read more about Lagged Fibonacci Generator: Properties of Lagged Fibonacci Generators, Problems With LFGs, Usage
Famous quotes containing the words lagged and/or generator:
“When any lagged behind, the cry of “blueberries” was most effectual to bring them up.”
—Henry David Thoreau (1817–1862)
“He admired the terrible recreative power of his memory. It was only with the weakening of this generator whose fecundity diminishes with age that he could hope for his torture to be appeased. But it appeared that the power to make him suffer of one of Odette’s statements seemed exhausted, then one of these statements on which Swann’s spirit had until then not dwelled, an almost new word relayed the others and struck him with new vigor.”
—Marcel Proust (1871–1922)