The Lagged Fibonacci Generator Family

History

Around the same time that Linear Congruential Generators became well known, another variant of the Lehmer Generator was proposed. With this method, new random numbers are created by drawing samples from previous results and using them as operands.

In practice, this generator uses the following equation:

X_n = X_j ☆ X_k mod M

In this equation, j and k are constants that refer to the result from a given number of steps back. For example, if j = 10, then X_j is the result from 10 steps ago. The ☆ symbol represents the operation being performed, such as addition or multiplication.

Generally speaking, implementations of these generators provide storage for k results. This also means that the storage requirements for their state can be quite large.

An additional issue for LFGs is that they are very dependent on their initialization. Often, the initial output from a simpler PRNG, such as a LCG, is used to seed the array of old results.

For this study, the following values are used by each LFG:

• J = 24
• K = 55
• M = 2³⁰ - 3

Additionally, the generator's array of previous values is seeded using our implementation of glibc's LCG generator. This is also reflected in the value of M, which is based on the highest possible number that could be used as a seed value.

Tested Variants

Additive Lagged Fibonacci Generator
An example implementation that uses addition as its operation.

Subtractive Lagged Fibonacci Generator
An example implementation that uses subtraction as its operation.

Multiplicative Lagged Fibonacci Generator
An example implementation that uses multiplication as its operation.