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

遅延フィボナッチ生成器（LFG、またはLFibとも呼ばれる）は、擬似乱数生成器の一例です。このクラスの乱数生成器は、「標準的な」線形合同型生成器の改良を目指しています。これらはフィボナッチ数列の一般化に基づいています。

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

S_{n}=S_{n-1}+S_{n-2

したがって、新しい項は数列の最後の2つの項の和となります。これは数列に一般化できます。

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

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

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

加算演算を使用する場合、生成器は加法遅れフィボナッチ生成器（ALFG）、乗算演算を使用する場合は乗法遅れフィボナッチ生成器（MLFG）、XOR演算を使用する場合は2タップ一般化フィードバックシフトレジスタ（GFSR）と呼ばれます。メルセンヌツイスターアルゴリズムはGFSRのバリエーションです。GFSRは線形フィードバックシフトレジスタ（LFSR）とも関連があります。

遅延フィボナッチ生成器の特性

遅延フィボナッチ生成器の最大周期は、二項演算に依存します。加算または減算を使用する場合、最大周期は(2 ^k − 1) × 2 ^M⁻¹です。乗算を使用する場合、最大周期は(2 ^k − 1) × 2 ^M⁻³、つまり加法演算の場合の周期の1/4です。ビット単位の排他的論理和を使用する場合、最大周期は2 ^k − 1です。 $\star$

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

y = x ^k + x ^j + 1

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

原始多項式のよく使われる次数ペア^{[ 1 ]}^{[ 2 ]}
j	7	5	24	65	128	6	31	97	353	168	334	273	418
け	10	17	55	71	159	31	63	127	521	521	607	607	1279

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 ]}

LFGの問題点

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

実装例

C言語による簡単な実装は以下のようになります。この実装では64ビットワードを使用し、周期は(2 ⁶⁰⁷ -1) × 2 ^63です。

#R を定義 (607) #S を定義 (273)#include <stdint.h>uint64_t X [ R ];uint64_t gen_rand () { static int j = S - 1 , k = R - 1 ; uint64_t r ; r = X [ k ] = X [ k ] + X [ j -- ] ; k -- ; if ( j < 0 ) j = R - 1 ; else if ( k < 0 ) k = R - 1 ; return r ; }

使用法

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

参照

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

参考文献

普遍的な乱数生成器に向けて、G.Marsaglia、A.Zaman

^ “RN Chapter” . www.ccs.uky.edu . 2004年3月9日時点のオリジナルよりアーカイブ。 2022年1月13日閲覧。
^ 「SPRNG: スケーラブルな並列擬似乱数生成ライブラリ」 . 2010年6月14日時点のオリジナルよりアーカイブ。2005年4月11日閲覧。
^並列乗法遅延フィボナッチジェネレータのパラメータ化、M. Mascagni、A. Srinivasan
^ ^a ^b「スーパーコンピュータのための一様乱数生成器」リチャード・ブレント、1992年
^「4タップシフトレジスタシーケンス乱数発生器」、ロバート・M・ジフ、Computers in Physics、12(4)、1998年7月/8月、pp. 385–392

[1] “RN Chapter” . www.ccs.uky.edu . 2004年3月9日時点のオリジナルよりアーカイブ。 2022年1月13日閲覧。

[2] 「SPRNG: スケーラブルな並列擬似乱数生成ライブラリ」 . 2010年6月14日時点のオリジナルよりアーカイブ。2005年4月11日閲覧。

[3] 並列乗法遅延フィボナッチジェネレータのパラメータ化、M. Mascagni、A. Srinivasan

[uniform-4] 「スーパーコンピュータのための一様乱数生成器」リチャード・ブレント、1992年

[5] 「4タップシフトレジスタシーケンス乱数発生器」、ロバート・M・ジフ、Computers in Physics、12(4)、1998年7月/8月、pp. 385–392

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[