Lagged Fibonacci generator

<h2 id="properties-of-lagged-fibonacci-generators">Properties of lagged Fibonacci generators</h2>
The maximum period of lagged Fibonacci generators depends on the binary operation 
 
 
 
 ⋆
 
 
 {\displaystyle \star }
 
. If addition or subtraction is used, the maximum period is (2k − 1) × 2M−1. If multiplication is used, the maximum period is (2k − 1) × 2M−3, or 1/4 of period of the additive case. If bitwise xor is used, the maximum period is 2k − 1.
For the generator to achieve this maximum period, the polynomial:

y = xk + xj + 1
must be <a href="/facts/Primitive_polynomial_(field_theory)/8nvXpBUL">primitive</a> over the integers mod 2. Values of j and k satisfying this constraint have been published in the literature. 

Popular pairs of primitive polynomial degrees<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a><a class="footnote-ref" id="fnref:2" href="#fn:2">2</a><table><tbody><tr><td>j</td><td>7</td><td>5</td><td>24</td><td>65</td><td>128</td><td>6</td><td>31</td><td>97</td><td>353</td><td>168</td><td>334</td><td>273</td><td>418</td></tr><tr><td>k</td><td>10</td><td>17</td><td>55</td><td>71</td><td>159</td><td>31</td><td>63</td><td>127</td><td>521</td><td>521</td><td>607</td><td>607</td><td>1279</td></tr></tbody></table>
Another list of possible values for j and k is on page 29 of volume 2 of <a href="/facts/The_Art_of_Computer_Programming/MR1bMD9e">The Art of Computer Programming</a>:

(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.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>
It has been suggested that good ratios between j and k are approximately the <a href="/facts/Golden_ratio/anloSRmD">golden ratio</a>.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>

<h2 id="problems-with-lfgs">Problems with LFGs</h2>
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. <a href="/facts/George_Marsaglia/Jlu1Defc">Marsaglia</a> 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 
 
 
 
 
 x
 
 n
 
 
 
 
 {\displaystyle x_{n}}
 
, 
 
 
 
 
 x
 
 n
 −
 a
 
 
 
 
 {\displaystyle x_{n-a}}
 
, and 
 
 
 
 
 x
 
 n
 −
 b
 
 
 
 
 {\displaystyle x_{n-b}}
 
, simply given by the generator itself ... While these correlations are spread over the size 
 
 
 
 p
 =
 m
 a
 x
 (
 a
 ,
 b
 ,
 c
 ,
 …
 )
 
 
 {\displaystyle p=max(a,b,c,\ldots )}
 
 of the generator itself, they can evidently still lead to significant errors.".<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> 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 <a href="/facts/Diehard_tests/6jj2Kylt">Birthday Spacings</a> and Generalized Triple tests.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>

<h2 id="example-implementation">Example implementation</h2>
A simple implementation in the <a href="/facts/C_(programming_language)/Ky2No763">C</a> programming language may look as shown below. This implementation uses 64-bit words and has a period of (2607 -1) × 263

#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;
}

<h2 id="usage">Usage</h2>
<ul><li><a href="/facts/Freeciv/yeStt1Mo">Freeciv</a> uses a lagged Fibonacci generator with {j = 24, k = 55} for its random number generator.</li>
<li>The <a href="/facts/Boost_library/vGLGG51A">Boost library</a> includes an implementation of a lagged Fibonacci generator.</li>
<li><a href="/facts/Subtract_with_carry/h8uwHE7g">Subtract with carry</a>, a lagged Fibonacci generator engine, is included in the <a href="/facts/C%252B%252B11/fI3YCoKQ">C++11</a> library.</li>
<li>The <a href="/facts/Oracle_Database/FHv5g732">Oracle Database</a> implements this generator in its DBMS_RANDOM package (available in Oracle 8 and newer versions).</li></ul>
<h2 id="see-also">See also</h2>
Wikipedia page '<a href="/facts/List_of_random_number_generators/oWbCuAdA">List of random number generators</a>' lists other PRNGs including some with better statistical qualitites:

<ul><li><a href="/facts/Linear_congruential_generator/E4PyJQ5U">Linear congruential generator</a></li>
<li><a href="/facts/ACORN_(PRNG)/FJDJggWV">ACORN generator</a></li>
<li><a href="/facts/Mersenne_Twister/R6Knca0q">Mersenne Twister</a></li>
<li><a href="/facts/Xoroshiro128%252B/Nna3MRak">Xoroshiro128+</a></li>
<li><a href="/facts/FISH_(cipher)/IP0xfavg">FISH (cipher)</a></li>
<li><a href="/facts/Pike_(cipher)/n3xEE9l9">Pike</a></li>
<li><a href="/facts/VIC_cipher/RbCJaPgv">VIC cipher</a></li></ul>

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

<h2 id="references">References</h2>

<ol>
<li id="fn:1">"RN Chapter". www.ccs.uky.edu. Archived from the original on 9 March 2004. Retrieved 13 January 2022. <a href="https://web.archive.org/web/20040309175607/http://www.ccs.uky.edu/csep/RN/RN.html" target="_blank">https://web.archive.org/web/20040309175607/http://www.ccs.uky.edu/csep/RN/RN.html</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">"SPRNG: Scalable Parallel Pseudo-Random Number Generator Library". Archived from the original on 2010-06-14. Retrieved 2005-04-11. <a href="https://web.archive.org/web/20100614213822/http://www.nersc.gov/nusers/resources/software/libs/math/random/www2.0/DOCS/www/parameters.html" target="_blank">https://web.archive.org/web/20100614213822/http://www.nersc.gov/nusers/resources/software/libs/math/random/www2.0/DOCS/www/parameters.html</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Parameterizing Parallel Multiplicative Lagged-Fibonacci Generators, M. Mascagni, A. Srinivasan <a href="http://www.cs.fsu.edu/~asriniva/papers/mlfg.ps" target="_blank">http://www.cs.fsu.edu/~asriniva/papers/mlfg.ps</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">"Uniform random number generators for supercomputers", Richard Brent, 1992 <a href="https://openresearch-repository.anu.edu.au/bitstream/1885/40805/3/TR-CS-92-02.pdf" target="_blank">https://openresearch-repository.anu.edu.au/bitstream/1885/40805/3/TR-CS-92-02.pdf</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">"Four-tap shift-register-sequence random-number generators", Robert M. Ziff, Computers in Physics, 12(4), Jul/Aug 1998, pp. 385–392 <a href="https://arxiv.org/abs/cond-mat/9710104" target="_blank">https://arxiv.org/abs/cond-mat/9710104</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">"Uniform random number generators for supercomputers", Richard Brent, 1992 <a href="https://openresearch-repository.anu.edu.au/bitstream/1885/40805/3/TR-CS-92-02.pdf" target="_blank">https://openresearch-repository.anu.edu.au/bitstream/1885/40805/3/TR-CS-92-02.pdf</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
</ol>

Lagged Fibonacci generator open-in-new

Lagged Fibonacci generator