Lagged Fibonacci 法の性質

ウィキペディア小見出し辞書

Lagged Fibonacci 法の性質

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/20 15:49 UTC 版)

「Lagged Fibonacci 法」の記事における「Lagged Fibonacci 法の性質」の解説

Lagged Fibonacci 法の最大周期は、二項演算として加算か減算を使った場合は (2k − 1) × 2M − 1 となり、XOR を使った場合は (2k − 1) となる。乗算を使うと (2k − 1) × 2M − 3 となり、加減算を用いた場合の 1/4 になる。 最大周期を達成するには、多項式 y = xk + 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つは奇数にする必要がある。