時滯斐波那契生成器
時滯斐波那契生成器(英語:Lagged Fibonacci generator,簡稱:LFG或LFib),是一類偽隨機數生成器。用於改進標準的線性同餘生成器。
用遞推關係表示序列的生成:
其中,新項由兩個老項計算生成。m通常是2的冪 (m = 2M), 經常232或264。其中 算符表示一般的二元運算符,這可以是加法、減法、乘法或者位運算異或。相應地稱作加法時滯斐波那契生成器(ALFG)、乘法時滯斐波那契生成器(MLFG)、 雙抽頭廣義反饋移位寄存器(GFSR)。梅森旋轉算法是GFSR的變種。GFSR與線性反饋移位寄存器有關。
使用k個狀態字的生成器,稱作'記住'了過去k個值。
時滯斐波那契生成器的理論相當複雜,理論也不夠充分到能指導如何選擇j與k。生成器的初始化也非常敏感。
性值
時滯斐波那契生成器對於加減法運算,有最大周期(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] (頁面存檔備份,存於互聯網檔案館)
另一套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]
時滯斐波那契生成器的問題
Robert M. Ziff在四抽頭移位寄存器的論文中指出「眾所周知這種生成器,特別是雙抽頭的 R(103, 250),有嚴重的缺陷。George Marsaglia發現R(24, 55)與更小的生成器的作為相當差,並建議不要用這類生成器。 ... 雙抽頭生成器R(a, b)的基礎問題是給定了生成器,則有內在的三點相關: , , 。這種相關性在 尺度上傳播,顯然導致了問題。」[3]這是指標準的時滯斐波那契生成器,每個新數依賴於以前的2個老數。三抽頭的時滯斐波那契生成器去除了很多統計問題,如在Birthday Spacings與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