Editing Lagged Fibonacci generator (section)

== 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>