(If you don't yet know what a PRNG is, go here. Added upon request by Gorgonzola and foreverchanges.)

Lagged Fibonacci PRNGs are a congruential kind of PRNG (because of the way they use modular arithmetic to bring the output into range), but are rather general in description (you can get more specific, e.g. modified Lagged Fibonacci PRNG, multiplicative LFPRNG, and so on). LF PRNGs can be made to have surprisingly high periods for even small parameters.

Assuming that X1, X2, X3, X4... is the output of the PRNG, and that the output is in the range 0..Z, they are of the form:

Xn = f(Xn-p, Xn-q) mod Z

where p and q are the integer 'lags' (q>p>0) and where f() is a function which takes Xn-p and Xn-q and outputs a single integer. The two most commonly used functions are the multiplicative function (multiplication) or the additive function (addition):

Xn = (Xn-p * Xn-q) mod Z

or

Xn = (Xn-p + Xn-q) mod Z

The typical way in which Fibonacci PRNGs are represented is LFG(p, q, Z) where p and q are the lags and Z the modulus.
Fibonacci PRNGs can be very effective. Assuming that the modulus Z is of the form 2n, then if p, q and the seed values (X0 to Xq-1, assuming that q>p) are correctly picked, the period of the generator is (2p - 1) * (2n-1).


The contents of this writeup are in the public domain.

Log in or register to write something here or to contact authors.