What (who) is lagged up - definition

A Lagged Fibonacci generator (LFG or sometimes LFib) 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:

${\displaystyle S_{n}=S_{n-1}+S_{n-2}}$

Hence, the new term is the sum of the last two terms in the sequence. This can be generalised to the sequence:

${\displaystyle S_{n}\equiv S_{n-j}\star S_{n-k}{\pmod {m}},0<j<k}$

In which case, the new term is some combination of any two previous terms. m is usually a power of 2 (m = 2^M), often 2³² or 2⁶⁴. The ${\displaystyle \star }$ operator denotes a general binary operation. This may be either addition, subtraction, multiplication, or the bitwise 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.