(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 X_{1}, X_{2}, X_{3}, X_{4}... is the output of the PRNG, and that the output is in the range 0..Z, they are of the form:

X_{n} = *f*(X_{n-p}, X_{n-q}) mod Z

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

X_{n} = (X_{n-p} * X_{n-q}) mod Z

or

X_{n} = (X_{n-p} + X_{n-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 2^{n}, then if p, q and the seed values (X_{0} to X_{q-1}, assuming that q>p) are correctly picked, the period of the generator is (2^{p} - 1) * (2^{n-1}).

The contents of this writeup are in the public domain.