时滞斐波那契生成器

时滞斐波那契生成器（Lagged Fibonacci generator，LFG或LFib），是一类伪随机数生成器。用于改进标准的线性同余生成器。

用递推关系表示序列的生成：

S_{n}\equiv S_{n-j}\star S_{n-k}{\pmod {m}},0<j<k

其中，新项由两个老项计算生成。m通常是2的幂 (m = 2^M), 经常2³²或2⁶⁴。其中 $\star$ 算符表示一般的二元运算符，这可以是加法、减法、乘法或者位运算异或。相应地称作加法时滞斐波那契生成器（ALFG）、乘法时滞斐波那契生成器（MLFG）、双抽头广义反馈移位寄存器（GFSR）。梅森旋转算法是GFSR的变种。GFSR与线性反馈移位寄存器有关。

使用k个状态字的生成器，称作'记住'了过去k个值。

时滞斐波那契生成器的理论相当复杂，理论也不够充分到能指导如何选择j与k。生成器的初始化也非常敏感。

性值

时滞斐波那契生成器对于加减法运算，有最大周期(2^k - 1)*2^M-1；对异或运算有最大周期(2^k − 1) × k；对乘法运算的最大周期为(2^k − 1) × 2^M−3, 即加法运算最大周期的1/4.

为了达到最大周期，多项式:

y = x^k + x^j + 1

必须是{{tsl|en|primitive polynomial (field theory)|本原多项式]]，对于mod 2的整数. 满足这样的约束的j与k，已经在文献中公布，常用的有:

{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] （页面存档备份，存于互联网档案馆）

另一套j与k的可能值在《计算机程序设计艺术》第2卷第29页公布:

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

注意到上述数越小，周期就越短。

如果使用加法，要求前k个初始化生成器的值中至少一个是奇数。如果使用乘法，要求前k个值都必须是奇数.^[1]

有研究建议j与k最好近似黄金比例.^[2]

时滞斐波那契生成器的问题

Robert M. Ziff在四抽头移位寄存器的论文中指出“众所周知这种生成器，特别是双抽头的 R(103, 250)，有严重的缺陷。{{tsl en|George Marsaglia}}发现R(24, 55)与更小的生成器的作为相当差，并建议不要用这类生成器。 ... 双抽头生成器R(a, b)的基础问题是给定了生成器，则有内在的三点相关： $x_{n}$ , $x_{n-a}$ , $x_{n-b}$ 。这种相关性在 $p=max(a,b,c,\ldots )$ 尺度上传播，显然导致了问题。”^[3]这是指标准的时滞斐波那契生成器，每个新数依赖于以前的2个老数。三抽头的时滞斐波那契生成器去除了很多统计问题，如在Birthday Spacings（英语：Diehard tests）与Generalized Triple测试失败问题.^[2]

时滞斐波那契生成器的初始化是个非常复杂的问题。时滞斐波那契生成器的输出对其初始化条件非常敏感。时滞斐波那契生成器的数学理论是不完备的，使它依赖于统计测试而不是理论分析。

使用

Freeciv游戏使用时滞斐波那契生成器{j = 24, k = 55}。
Boost C++ Libraries实现了时滞斐波那契生成器。
Subtract with carry是时滞斐波那契生成器的一种实现，包含在C++11标准模板库中。
Oracle数据库在DBMS_RANDOM包中实现了时滞斐波那契生成器。

参考文献

Toward a universal random number generator, G.Marsaglia, A.Zaman

^ Parameterizing Parallel Multiplicative Lagged-Fibonacci Generators （页面存档备份，存于互联网档案馆）, M.Mascagni, A.Srinivasan
^ ^2.0 ^2.1 "Uniform random number generators for supercomputers" （页面存档备份，存于互联网档案馆）, Richard Brent, 1992
^ "Four-tap shift-register-sequence random-number generators" （页面存档备份，存于互联网档案馆）, Robert M. Ziff, Computers in Physics, 12(4), Jul/Aug 1998, pp. 385–392

[1] Parameterizing Parallel Multiplicative Lagged-Fibonacci Generators （页面存档备份，存于互联网档案馆）, M.Mascagni, A.Srinivasan

[uniform-2] 2.0 ^2.1 "Uniform random number generators for supercomputers" （页面存档备份，存于互联网档案馆）, Richard Brent, 1992

[3] "Four-tap shift-register-sequence random-number generators" （页面存档备份，存于互联网档案馆）, Robert M. Ziff, Computers in Physics, 12(4), Jul/Aug 1998, pp. 385–392

[1]

[2]

[3]