時滯斐波那契生成器

時滯斐波那契生成器（英語：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

必須是本原多項式，對於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個值都必須是奇數.

有研究建議j與k最好近似黃金比例.

時滯斐波那契生成器的問題

Robert M. Ziff在四抽頭移位寄存器的論文中指出「眾所周知這種生成器，特別是雙抽頭的 R(103, 250)，有嚴重的缺陷。George Marsaglia發現R(24, 55)與更小的生成器的作為相當差，並建議不要用這類生成器。 ... 雙抽頭生成器R(a, b)的基礎問題是給定了生成器，則有內在的三點相關：$x_{n}$, $x_{n-a}$, $x_{n-b}$。這種相關性在$p=max(a,b,c,\ldots )$尺度上傳播，顯然導致了問題。」這是指標準的時滯斐波那契生成器，每個新數依賴於以前的2個老數。三抽頭的時滯斐波那契生成器去除了很多統計問題，如在Birthday Spacings與Generalized Triple測試失敗問題.

時滯斐波那契生成器的初始化是個非常複雜的問題。時滯斐波那契生成器的輸出對其初始化條件非常敏感。時滯斐波那契生成器的數學理論是不完備的，使它依賴於統計測試而不是理論分析。

使用

• 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