|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 付 ： [ふ] 1. (n,vs) giving to 2. submitting to 3. refer to 4. affix 5. append
Lagged Fibonacci 法（ラグ付フィボナッチ法）は疑似乱数生成法の１つ。この手法は標準的な線形合同法を改善する事を目的としており、フィボナッチ数の生成法を元にしている。 フィボナッチ数列は以下の漸化式により表現される。 : つまり、数列の前二項の和が次の項になる。これは以下のように一般化できる。 : ここで、★演算子は一般的な二項演算子を表し、新しい項は以前の何らかの二項を演算して得られる。★演算子は加算にも減算にも乗算にもビット単位の排他的論理和にもなる。''m'' は通常2の累乗（''m'' = 2''M''）で、232 か 264 がよく使われる。この種の生成法の理論はかなり複雑であり、''j'' と ''k'' により乱数を選ぶのは容易い事ではないだろう。また、この生成法は初期化の仕方にとても敏感な傾向もある。 この手法にはサイズ ''k'' の領域を必要とする（最後の ''k'' 個の要素を覚えておく）。 二項演算として加算を行った場合、この方法は「加算 Lagged Fibonacci 法（ALFG）」となる。乗算を使えば「乗算 Lagged Fibonacci 法（MLFG）」となり、XORを使うと「2タップ一般化帰還シフトレジスタ（GFSR）」となる。メルセンヌ・ツイスタ法はGFSRの一種である。GFSRは線形帰還シフトレジスタ（LFSR）とも関連がある。 == Lagged Fibonacci 法の性質 == Lagged Fibonacci 法の最大周期は、二項演算として加算か減算を使った場合は (2''k'' − 1) × 2''M'' − 1 となり、XOR を使った場合は (2''k'' − 1) となる。乗算を使うと (2''k'' − 1) × 2''M'' − 3 となり、加減算を用いた場合の 1/4 になる。 最大周期を達成するには、多項式 :''y'' = ''x''''k'' + ''x'' ''j'' + 1 は modulo 2 の整数において原始的でなくてはならない。この条件を満たす ''j'' と ''k'' の組は文献に記されている。有名なものとしては、次のようなものがある（(''j'', ''k'') の順で記してある）。 :(7,10), (5,17), (24,55), (65,71), (128,159) :(6,31), (31,63), (97,127), (353,521), (168,521), (334,607), (273,607), (418,1279) ''The Art of Computer Programming'' の volume 2 の 28 ページには、以下のようにその他の ''j'' と ''k'' の組も記されている（既に上で示したものは太字にしてある）。 :(1,2), (1,3), (2,3), (1,4), (3,4), (2,5), (3,5), (1,6), (5,6), (1,7), (6,7), (3,7), (4,7), (4,9), (5,9), (3,10), (7,10), (2,11), (9,11), (1,15), (14,15), (4,15), (11,15), (7,15), (8,15), (3,17), (14,17), (5,17), (12,17), (6,17), (11,17), (7,18), (11,18), (3,20), (17,20), (2,21), (19,21), (1,22), (21,22), (5,23), (18,23), (9,23), (14,23), (3,25), (22,25), (7,25), (18,25), (3,28), (25,28), (9,28), (19,28), (13,28), (15,28), (2,29), (27,29), (3,31), (28,31), (6,31), (25,31), (7,31), (24,31), (13,31), (18,31), (13,33), (20,33), (2,35), (33,35), (11,36), (25,36), (4,39), (35,39), (8,39), (31,39), (14,39), (25,39), (3,41), (38,41), (20,41), (21,41), (5,47), (42,47), (14,47), (33,47), (20,47), (27,47), (21,47), (26,47), (9,49), (40,49), (12,49), (37,49), (15,49), (34,49), (22,49), (27,49), (3,52), (49,52), (19,52), (33,52), (21,52), (31,52), (24,55), (31,55), (7,57), (50,57), (22,57), (35,57), (19,58), (39,58), (1,60), (59,60), (11,60), (49,60), (1,63), (62,63), (5,63), (58,63), (31,63), (32,63), (18,65), (47,65), (32,65), (33,65), (9,68), (59,68), (33,68), (35,68), (6,71), (65,71), (9,71), (62,71), (18,71), (53,71), (20,71), (51,71), (35,71), (36,71), (25,73), (48,73), (28,73), (45,73), (31,73), (42,73), (9,79), (70,79), (19,79), (60,79), (4,81), (77,81), (16,81), (65,81), (35,81), (46,81), (13,84), (71,84), (13,87), (74,87), (38,89), (51,89), (2,93), (91,93), (21,94), (73,94), (11,95), (84,95), (17,95), (78,95), (6,97), (91,97), (12,97), (85,97), (33,97), (64,97), (34,97), (63,97), (11,98), (87,98), (27,98), (71,98) 小さい数であるほど周期が小さい点には注意する（最初の''乱数''が再び現れるまでにほんの少しの''乱数''しか現れない）。 乱数種の ''k'' 個の値のうち最低でも1つは奇数にする必要がある。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Lagged Fibonacci 法」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 Lagged Fibonacci generator 」があります。 スポンサード リンク
|