About: Lagged Fibonacci 法

Lagged Fibonacci 法（ラグ付フィボナッチ法）は擬似乱数生成法の１つ。この手法は標準的な線形合同法を改善する事を目的としており、フィボナッチ数の生成法を元にしている。 フィボナッチ数列は以下の漸化式により表現される。 つまり、数列の前二項の和が次の項になる。これは以下のように一般化できる。 ここで、★演算子は一般的な二項演算子を表し、新しい項は以前の何らかの二項を演算して得られる。★演算子は加算にも減算にも乗算にもビット単位の排他的論理和にもなる。m は通常2の累乗（m = 2M）で、232 か 264 がよく使われる。この種の生成法の理論はかなり複雑であり、j と k により乱数を選ぶのは容易い事ではないだろう。また、この生成法は初期化の仕方にとても敏感な傾向もある。 この手法にはサイズ k の領域を必要とする（最後の k 個の要素を覚えておく）。 二項演算として加算を行った場合、この方法は「加算 Lagged Fibonacci 法（ALFG）」となる。乗算を使えば「乗算 Lagged Fibonacci 法（MLFG）」となり、XORを使うと「2タップ一般化帰還シフトレジスタ（GFSR）」となる。メルセンヌ・ツイスタ法はGFSRの一種である。GFSRは線形帰還シフトレジスタ（LFSR）とも関連がある。