Lagged Fibonacci generator

A Lagged Fibonacci generator (LFG or sometimes LFib) is an example of a <a href="/facts/Pseudorandom_number_generator/sIrCxIBq">pseudorandom number generator</a>. This class of <a href="/facts/Random_number_generator/RtXEfbzd">random number generator</a> is aimed at being an improvement on the 'standard' <a href="/facts/Linear_congruential_generator/E4PyJQ5U">linear congruential generator</a>. These are based on a generalisation of the <a href="/facts/Fibonacci_sequence/mqxpAUQD">Fibonacci sequence</a>.
The Fibonacci sequence may be described by the <a href="/facts/Recurrence_relation/JolXC71M">recurrence relation</a>:

S
          
            n
          
        
        =
        
          S
          
            n
            −
            1
          
        
        +
        
          S
          
            n
            −
            2
          
        
      
    
    {\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:

S
 
 n
 
 
 ≡
 
 S
 
 n
 −
 j
 
 
 ⋆
 
 S
 
 n
 −
 k
 
 
 
 
 (
 mod
 
 m
 )
 
 ,
 0
 <
 j
 <
 k
 
 
 {\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 = 2M), often 232 or 264. The 
 
 
 
 ⋆
 
 
 {\displaystyle \star }
 
 operator denotes a general <a href="/facts/Binary_operation/CYtow0bz">binary operation</a>. This may be either addition, subtraction, multiplication, or the <a href="/facts/Bitwise_operation/0gkqnUda">bitwise</a> exclusive-or operator (<a href="/facts/XOR/FHyr7hGQ">XOR</a>). 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 <a href="/facts/Generalised_feedback_shift_register/22pktBbX">generalised feedback shift register</a> or GFSR. The <a href="/facts/Mersenne_Twister/R6Knca0q">Mersenne Twister</a> algorithm is a variation on a GFSR. The GFSR is also related to the <a href="/facts/Linear-feedback_shift_register/22pktBbX">linear-feedback shift register</a>, or LFSR.

Lagged Fibonacci generator open-in-new

Lagged Fibonacci generator