Lagged Fibonacci generator

related topics
{math, number, function}
{rate, high, increase}

A Lagged Fibonacci generator (LFG) is an example of a pseudorandom number generator. This class of random number generator is aimed at being an improvement on the 'standard' linear congruential generator. These are based on a generalisation of the Fibonacci sequence.

The Fibonacci sequence may be described by the recurrence relation:

Hence, the new term is the sum of the last two terms in the sequence. This can be generalised to the sequence:

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 \star operator denotes a general binary operation. This may be either addition, subtraction, multiplication, or the bitwise arithmetic exclusive-or operator (XOR). 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 generalised feedback shift register or GFSR. The Mersenne twister algorithm is a variation on a GFSR. The GFSR is also related to the Linear Feedback Shift Register, or LFSR.

Contents

Properties of lagged Fibonacci generators

Lagged Fibonacci generators have a maximum period of (2k - 1)*2M-1 if addition or subtraction is used, and (2k-1)*k if exclusive-or operations are used to combine the previous values. If, on the other hand, multiplication is used, the maximum period is (2k - 1)*2M-3, or 1/4 of period of the additive case.

For the generator to achieve this maximum period, the polynomial:

must be primitive over the integers mod 2. Values of j and k satisfying this constraint have been published in the literature. Popular pairs are:

Another list of possible values for j and k is on page 29 of volume 2 of The Art of Computer Programming:

Note that the smaller number have short periods (only a few "random" numbers are generated before the first "random" number is repeated and the sequence restarts).

It is required that at least one of the first k values chosen to initialise the generator be odd.

It has been suggested that good ratios between j and k are approximately the golden ratio[1].

Problems with LFGs

In a paper on four-tap shift registers, Robert M. Ziff states that "It is now widely known that such generators, in particular with the two-tap rules such as R(103, 250), have serious deficiencies. Marsaglia observed very poor behavior with R(24,55) and smaller generators, and advised against using generators of this type altogether. ... The basic problem of two-tap generators R(a, b) is that they have a built-in three-point correlation between xn, xna, and xnb, simply given by the generator itself ... While these correlations are spread over the size p = max(a, b, c, \ldots ) of the generator itself, they can evidently still lead to significant errors."[2].

Full article ▸

related documents
Brun's constant
Sum rule in differentiation
Column vector
Product of rings
Abelian category
Elias delta coding
Endomorphism
Category of sets
Complete category
Inverse functions and differentiation
Sharp-P
Hamiltonian path problem
Double precision
Characteristic subgroup
Mutual recursion
Random sequence
Inequation
Kleene star
AVL tree
Additive function
Baire category theorem
Identity matrix
Sophie Germain prime
Axiom of union
Up to
Hausdorff maximal principle
Subset
Row and column spaces
Complete measure
Normal morphism