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. A pseudorandom number generator (PRNG) is an algorithm that generates a sequence of numbers which are not truly random. ... A random number generator is a computational or physical device designed to generate a sequence of elements (usually numbers), such that the sequence can be used as a random one. ... Linear congruential generators (LCGs) represent one of the oldest and best-known pseudorandom number generator algorithms. ... In mathematics, the Fibonacci numbers form a sequence defined recursively by: In words: you start with 0 and 1, and then produce the next Fibonacci number by adding the two previous Fibonacci numbers. ...

The Fibonacci sequence may be described by the recurrence relation: In mathematics, a recurrence relation, also known as a difference equation, is an equation which defines a sequence recursively: each term of the sequence is defined as a function of the preceding terms. ...

S_n = S_{n − 1} + S_{n − 2}

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 = 2^M), often 2³² or 2⁶⁴. The 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. In mathematics, a binary operation is a calculation involving two input quantities, in other words, an operation whose arity is two. ... In computer programming, a bitwise operation operates on one or two bit patterns or binary numerals at the level of their individual bits. ... Exclusive disjunction (usual symbol xor) is a logical operator that results in true if one of the operands (not both) is true. ...

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 Mersenne twister is a pseudorandom number generator developed in 1997 by Makoto Matsumoto (松本 眞) and Takuji Nishimura (西村 拓士)[1] that is based on a matrix linear recurrence over a finite binary field . ...

Properties of Lagged Fibonacci Generators

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

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

y = x^k + x^j + 1

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: A primitive polynomial may refer to one of two concepts, which are : A polynomial over a unique factorization domain (such as the integers) whose greatest common divisor of its coefficients is one. ...

{j = 7, k = 10}, {j = 5, k = 17}, {j = 24, k = 55}, {j = 65, k = 71}, {j = 128, k = 159} [1], {j = 6, k = 31}, {j = 31, k = 63}, {j = 97, k = 127}, {j = 353, k = 521}, {j = 168, k = 521}, {j = 334, k = 607}, {j = 273, k = 607}, {j = 418, k = 1279} [2]

Another list of possible values for j and k is on page 28 of volume 2 of The Art of Computer Programming; the values listed above are in bold face: Cover of books The Art of Computer Programming[1] is a comprehensive monograph written by Donald Knuth which covers many kinds of programming algorithms and their analysis. ...

(1,2), (1,3), (2,3), (1,4), (3,4), (2,5), (3,5), (1,6), (5,6), (1,7), (6,7), (3,7), (4,7), (4,9), (5,9), (3,10), (7,10), (2,11), (9,11), (1,15), (14,15), (4,15), (11,15), (7,15), (8,15), (3,17), (14,17), (5,17), (12,17), (6,17), (11,17), (7,18), (11,18), (3,20), (17,20), (2,21), (19,21), (1,22), (21,22), (5,23), (18,23), (9,23), (14,23), (3,25), (22,25), (7,25), (18,25), (3,28), (25,28), (9,28), (19,28), (13,28), (15,28), (2,29), (27,29), (3,31), (28,31), (6,31), (25,31), (7,31), (24,31), (13,31), (18,31), (13,33), (20,33), (2,35), (33,35), (11,36), (25,36), (4,39), (35,39), (8,39), (31,39), (14,39), (25,39), (3,41), (38,41), (20,41), (21,41), (5,47), (42,47), (14,47), (33,47), (20,47), (27,47), (21,47), (26,47), (9,49), (40,49), (12,49), (37,49), (15,49), (34,49), (22,49), (27,49), (3,52), (49,52), (19,52), (33,52), (21,52), (31,52), (24,55), (31,55), (7,57), (50,57), (22,57), (35,57), (19,58), (39,58), (1,60), (59,60), (11,60), (49,60), (1,63), (62,63), (5,63), (58,63), (31,63), (32,63), (18,65), (47,65), (32,65), (33,65), (9,68), (59,68), (33,68), (35,68), (6,71), (65,71), (9,71), (62,71), (18,71), (53,71), (20,71), (51,71), (35,71), (36,71), (25,73), (48,73), (28,73), (45,73), (31,73), (42,73), (9,79), (70,79), (19,79), (60,79), (4,81), (77,81), (16,81), (65,81), (35,81), (46,81), (13,84), (71,84), (13,87), (74,87), (38,89), (51,89), (2,93), (91,93), (21,94), (73,94), (11,95), (84,95), (17,95), (78,95), (6,97), (91,97), (12,97), (85,97), (33,97), (64,97), (34,97), (63,97), (11,98), (87,98), (27,98), (71,98)

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^{[citation needed]}. The golden section is a line segment sectioned into two according to the golden ratio. ...

Problems with LFGs

The initialisation of LFGs is a very complex problem; any maximum period LFG has a large number of possible cycles, all different. Choosing a cycle is possible, but methods for doing this may endanger the randomness of subsequent outputs. Secondly, the output of LFGs is very sensitive to initial conditions, and statistical defects may appear initially but also periodically in the output sequence unless extreme care is taken. Another potential problem with LFGs is that the mathematical theory behind them is incomplete, making it necessary to rely on statistical tests rather than theoretical performance. These reasons, combined with the existence of the free and very high-quality Mersenne twister algorithm tend to make 'home-brewed' implementations of LFGs less than desirable in the presence of superior alternatives. The Mersenne twister is a pseudorandom number generator developed in 1997 by Makoto Matsumoto (松本 眞) and Takuji Nishimura (西村 拓士)[1] that is based on a matrix linear recurrence over a finite binary field . ...

Usage

• Freeciv uses a lagged Fibonacci generator with {j = 24, k = 55} for its random number generator.
• The Boost library includes an implementation of a lagged Fibonacci generator.
• MATLAB uses a {j=??, k = 32} generator for its rand() function (info here).
• The Oracle Database implements this generator in its DBMS_RANDOM package (available in Oracle 8 and newer versions).

Freeciv is a multiplayer, turn-based strategy game for personal computers inspired by the commercial proprietary Sid Meiers Civilization series. ... Boost is a collection of libraries that extend the functionality of C++. The libraries are licensed under the Boost Software License, a very open license designed to allow Boost to be used with any project. ... MATLAB is a numerical computing environment and programming language. ... An Oracle database consists of a collection of data managed by an Oracle database management system. ...

See also

• Linear congruential generator
• Mersenne twister
• FISH (cipher)
• Pike
• VIC cipher