遅延フィボナッチジェネレータ

遅延フィボナッチ ジェネレータ( LFGまたはLFib とも呼ばれる)は、疑似乱数ジェネレータの一例です。このクラスの乱数ジェネレータは、「標準」線形合同型ジェネレータの改良を目指しています。これらは、フィボナッチ数列の一般化に基づいています。

フィボナッチ数列は、次の再帰関係によって記述できます。

${\displaystyle S_{n}=S_{n-1}+S_{n-2}$

したがって、新しい項はシーケンスの最後の 2 つの項の合計です。これは次のシーケンスに一般化できます。

${\displaystyle S_{n}\equiv S_{nj}\star S_{nk}{\pmod {m}},0<j<k}$

この場合、新しい項は、前の 2 つの項の組み合わせになります。m は通常 2 の累乗 ( m = 2 ^M ) で、多くの場合 2 ³²または 2 ⁶⁴です。演算子は一般的な2 進演算を表します。これは、加算、減算、乗算、またはビットごとの排他的論理和演算子 ( XOR )のいずれかです。 このタイプのジェネレータの理論はかなり複雑で、 jとkにランダムな値を選択するだけでは十分ではない場合があります。 これらのジェネレータは、初期化の影響を非常に受けやすい傾向もあります。 ${\displaystyle \star}$

このタイプのジェネレーターは、kワードの状態を使用します (最後のk個の値を「記憶」します)。

使用される演算が加算の場合、ジェネレーターはAdditive Lagged Fibonacci Generator (ALFG) と呼ばれます。乗算が使用される場合はMultiplicative Lagged Fibonacci Generator (MLFG) と呼ばれます。XOR 演算が使用される場合はTwo-tap Generalised Feedback Shift Register (GFSR) と呼ばれます。Mersenne Twisterアルゴリズムは GFSR のバリエーションです。GFSR はLinear-Feedback Shift Register (LFSR)とも関連があります。

遅延フィボナッチ生成器の最大周期は、バイナリ演算によって異なります。加算または減算を使用する場合、最大周期は (2 ^k − 1) × 2 ^{M −1}です。乗算を使用する場合、最大周期は (2 ^k − 1) × 2 ^{M −3}、つまり加算の場合の周期の 1/4 です。ビット単位の排他的論理和を使用する場合、最大周期は 2 ^k − 1 です。 ${\displaystyle \star}$

ジェネレータがこの最大周期を達成するには、多項式が必要です。

y = xk + xj ⁺ 1^です

2を法とする整数に対して原始的でなければならない。この制約を満たすjとkの値は文献で発表されている。

jとkの可能な値の別のリストは、『The Art of Computer Programming』第 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個の値のうち少なくとも1つが奇数である必要があります。代わりに乗算を使用する場合、最初のk個の値すべてが奇数であること、さらにそのうちの少なくとも1つが±3 mod 8である必要があります。^[3]

jとkの間の良い比率はほぼ黄金比であると示唆されている。^[4]

4タップシフトレジスタに関する論文で、ロバート・M・ジフは、XOR演算子を使用するLFGについて、「現在では、このようなジェネレータ、特にR(103, 250)などの2タップルールのジェネレータには重大な欠陥があることが広く知られています。 マルサリアは、 R(24, 55)およびそれより小さいジェネレータで非常に悪い動作を観察し、このタイプのジェネレータの使用を一切控えるようアドバイスしました。... 2タップジェネレータR(a, b)の基本的な問題は、ジェネレータ自体によって単純に与えられる、、、およびの間に3点の相関関係が組み込まれていることです...これらの相関関係はジェネレータ自体のサイズ全体に広がっていますが、それでも明らかに重大なエラーにつながる可能性があります。」と述べています。^{[5]これは、シーケンス内の新しい数字がそれぞれ2つの前の数字に依存する標準的なLFGのみを指します。3タップLFGは、}誕生日間隔テストや一般化トリプルテストに失敗するなどの統計的問題を排除できることが示されています。^[4]${\displaystyle x_{n}}$${\displaystyle x_{na}}$${\displaystyle x_{nb}}$${\displaystyle p=max(a,b,c,\ldots )}$

• Freeciv は乱数ジェネレーターとして、{j = 24、k = 55} の遅延フィボナッチ ジェネレーターを使用します。
• Boostライブラリには、遅延フィボナッチ ジェネレーターの実装が含まれています。
• 遅延フィボナッチ生成エンジンであるSubtract with carry がC++11ライブラリに含まれています。
• Oracleデータベースは、このジェネレータを DBMS_RANDOM パッケージ (Oracle 8 以降のバージョンで使用可能) に実装します。

Wikipedia のページ「乱数ジェネレーターの一覧」には、統計品質が優れたものも含め、その他の PRNG がリストされています。

• 線形合同ジェネレータ
• ACORNジェネレータ
• メルセンヌツイスター
• ゾロシロ128+
• FISH（暗号）
• パイク
• VIC暗号

ユニバーサル乱数ジェネレータに向けて、G.Marsaglia、A.Zaman