時滯斐波那契生成器

時滯斐波那契生成器(英語:Lagged Fibonacci generator,簡稱:LFG或LFib),是一類偽隨機數生成器。用於改進標準的線性同餘生成器

遞推關係表示序列的生成:

其中,新項由兩個老項計算生成。m通常是2的冪 (m = 2M), 經常232或264。其中 算符表示一般的二元運算符,這可以是加法、減法、乘法或者位運算異或。相應地稱作加法時滯斐波那契生成器(ALFG)、乘法時滯斐波那契生成器(MLFG)、 雙抽頭廣義反饋移位寄存器(GFSR)。梅森旋轉算法是GFSR的變種。GFSR與線性反饋移位寄存器有關。

使用k個狀態字的生成器,稱作'記住'了過去k個值。

時滯斐波那契生成器的理論相當複雜,理論也不夠充分到能指導如何選擇jk。生成器的初始化也非常敏感。

性值

時滯斐波那契生成器對於加減法運算,有最大周期(2k - 1)*2M-1;對異或運算有最大周期(2k − 1) × k;對乘法運算的最大周期為(2k − 1) × 2M−3, 即加法運算最大周期的1/4.

為了達到最大周期,多項式:

y = xk + xj + 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]頁面存檔備份,存於互聯網檔案館

另一套jk的可能值在《電腦程式設計藝術》第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]

有研究建議jk最好近似黃金比例.[2]

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

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

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

使用

參考文獻

Toward a universal random number generator, G.Marsaglia, A.Zaman
  1. ^ Parameterizing Parallel Multiplicative Lagged-Fibonacci Generators頁面存檔備份,存於互聯網檔案館), M.Mascagni, A.Srinivasan
  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