Random Number Generation: Types and Techniques

Lagged Fibonacci generator. A major problem with simple linear algorithms is 

that the period is limited by m. With the lagged Fibonacci algorithm, much larger periods 

can be obtained. The basic form of this algorithm is s

i+1 

= s

i−p 

± s

i−q 

mod m (Chan, 

2009). This algorithm can be used in conjunction with addition, subtraction, 

multiplication, or even exclusive-or (XOR). Because multiple past values are used 

instead of just the previous value as in the linear algorithms, values can be repeated inside 

---

RANDOM NUMBER GENERATION                                                                             16 

 

the period without indicating a loop. In the Boost library implementation of this 

algorithm, p is set to 44497, q is 21034, and the resulting period is around 2

2300000

 (Chan, 

2009). A period of this size greatly reduces the likelihood of pattern recognition and 

secures the generator from the more basic forms of passive attacks.