Editing Lagged Fibonacci generator

A '''Lagged Fibonacci generator''' ('''LFG''' or sometimes '''LFib''') 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]]:

:<math>S_n = S_{n-1} + S_{n-2}</math>

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

:<math>S_n \equiv S_{n-j} \star S_{n-k}  \pmod{m},   0 < j < k</math>

In which case, the new term is some combination of any two previous terms. ''m'' is usually a power of 2 (''m'' = 2<sup>''M''</sup>), often 2<sup>32</sup> or 2<sup>64</sup>. The <math>\star</math> operator denotes a general [[binary operation]]. This may be either addition, subtraction, multiplication, or the [[bitwise operation|bitwise]] 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 {{var|j}} and {{var|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.

== Properties of lagged Fibonacci generators ==
The maximum period of lagged Fibonacci generators depends on the binary operation <math>\star</math>. If addition or subtraction is used, the maximum period is (2<sup>''k''</sup> − 1) × 2<sup>''M''−1</sup>. If multiplication is used, the maximum period is (2<sup>''k''</sup> − 1) × 2<sup>''M''−3</sup>, or 1/4 of period of the additive case. If bitwise xor is used, the maximum period is 2<sup>''k''</sup> − 1.

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

:''y'' = ''x''<sup>''k''</sup> + ''x''<sup>''j''</sup> + 1

must be [[primitive polynomial (field theory)|primitive]] over the integers mod 2. Values of ''j'' and ''k'' satisfying this constraint have been published in the literature. 
{| class="wikitable"
|+ Popular pairs of primitive polynomial degrees<ref>{{cite web |url=http://www.ccs.uky.edu/csep/RN/RN.html |title=RN Chapter |website=www.ccs.uky.edu |access-date=13 January 2022 |archive-url=https://web.archive.org/web/20040309175607/http://www.ccs.uky.edu/csep/RN/RN.html |archive-date=9 March 2004 |url-status=dead}}</ref><ref>{{Cite web |url=http://www.nersc.gov/nusers/resources/software/libs/math/random/www2.0/DOCS/www/parameters.html |title=SPRNG: Scalable Parallel Pseudo-Random Number Generator Library |access-date=2005-04-11 |archive-date=2010-06-14 |archive-url=https://web.archive.org/web/20100614213822/http://www.nersc.gov/nusers/resources/software/libs/math/random/www2.0/DOCS/www/parameters.html |url-status=dead }}</ref>
|-
| ''j''||  7 ||  5 || 24 || 65 || 128 ||  6 || 31 ||  97 || 353 || 168 || 334 || 273 || 418
|-
| ''k''|| 10 || 17 || 55 || 71 || 159 || 31 || 63 || 127 || 521 || 521 || 607 || 607 || 1279
|-
|}

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

:(24, 55), (38, 89), (37, 100), (30, 127), (83, 258), (107, 378), (273, 607), (1029, 2281), (576, 3217), (4187, 9689), (7083, 19937), (9739, 23209)

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).

If addition is used, it is required that at least one of the first ''k'' values chosen to initialise the generator be odd. If multiplication is used, instead, it is required that all the first ''k'' values be odd, and further that at least one of them is ±3 mod 8.<ref>[http://www.cs.fsu.edu/~asriniva/papers/mlfg.ps Parameterizing Parallel Multiplicative Lagged-Fibonacci Generators], M. Mascagni, A. Srinivasan</ref>

It has been suggested that good ratios between {{var|j}} and {{var|k}} are approximately the [[golden ratio]].<ref name="uniform">[https://openresearch-repository.anu.edu.au/bitstream/1885/40805/3/TR-CS-92-02.pdf "Uniform random number generators for supercomputers"], Richard Brent, 1992</ref>

== Problems with LFGs ==
In a paper on four-tap shift registers, [[Robert M. Ziff]], referring to LFGs that use the XOR operator, 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.  [[George Marsaglia|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 <math>x_{n}</math>, <math>x_{n-a}</math>, and <math>x_{n-b}</math>, simply given by the generator itself ... While these correlations are spread over the size <math>p = max(a, b, c, \ldots )</math> of the generator itself, they can evidently still lead to significant errors.".<ref>[https://arxiv.org/abs/cond-mat/9710104 "Four-tap shift-register-sequence random-number generators"], Robert M. Ziff, Computers in Physics, 12(4), Jul/Aug 1998, pp. 385–392</ref> This only refers to the standard LFG where each new number in the sequence depends on two previous numbers. A three-tap LFG has been shown to eliminate some statistical problems such as failing the [[Diehard tests|Birthday Spacings]] and Generalized Triple tests.<ref name="uniform" />

==Example implementation==
A simple implementation in the [[C (programming language)|C]] programming language may look as shown below. This implementation uses 64-bit words and has a period of (2<sup>607</sup> -1) × 2<sup>63</sup>
<syntaxhighlight lang="c">
#define R (607)
#define S (273)

#include <stdint.h>

uint64_t  X[R];

uint64_t  gen_rand()
{
    static int j = S - 1, k = R - 1;
	uint64_t  r;
    
    r = X[k] = X[k] + X[j--];
	k--;
	if (j < 0)
		j = R - 1;
	else if (k < 0)
		k = R - 1;
	return r;
}
</syntaxhighlight>

== 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.
* [[Subtract with carry]], a lagged Fibonacci generator engine, is included in the [[C++11]] library.
* The [[Oracle Database]] implements this generator in its DBMS_RANDOM package (available in Oracle 8 and newer versions).

== See also ==
Wikipedia page '[[List of random number generators]]' lists other PRNGs including some with better statistical qualities:
* [[Linear congruential generator]]
* [[ACORN (PRNG)|ACORN generator]]
* [[Mersenne Twister]]
* [[Xoroshiro128+]]
* [[FISH (cipher)]]
* [[Pike (cipher)|Pike]]
* [[VIC cipher]]

== References ==
:[https://web.archive.org/web/20100610050921/http://stat.fsu.edu/techreports/M766.pdf Toward a universal random number generator], G.Marsaglia, A.Zaman
<references/>

{{DEFAULTSORT:Lagged Fibonacci Generator}}
[[Category:Pseudorandom number generators]]
[[Category:Fibonacci numbers]]