Editing Lagged Fibonacci generator (section)

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]]:

:<math>S_n = S_{n-1} + S_{n-2}</math>

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

:<math>S_n \equiv S_{n-j} \star S_{n-k}  \pmod{m},   0 < j < k</math>

In which case, the new term is some combination of any two previous terms. ''m'' is usually a power of 2 (''m'' = 2<sup>''M''</sup>), often 2<sup>32</sup> or 2<sup>64</sup>. The <math>\star</math> operator denotes a general [[binary operation]]. This may be either addition, subtraction, multiplication, or the [[bitwise operation|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 {{var|j}} and {{var|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.