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: 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 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 and . 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. Properties of lagged Fibonacci generators The maximum period of lagged Fibonacci generators depends on the binary operation . If addition or subtraction is used, the maximum period is (2k − 1) × 2M−1. If multiplication is used, the maximum period is (2k − 1) × 2M−3, or 1/4 of period of the additive case. If bitwise xor is used, the maximum period is 2k − 1. For the generator to achieve this maximum period, the polynomial: y = xk + xj + 1 must be primitive over the integers mod 2. Values of j and k satisfying this constraint have been published in the literature. 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