Метод Фибоначчи с запаздываниями (Lagged Fibonacci generator)

The Fibonacci sequence may be described by the

S_n = S_{n − 1} + S_{n − 2}

Hence, the new term is the sum of the last two terms in the sequence. This can be generalised to the sequence:

In which case, the new term is some combination of any two previous terms. m is usually a power of 2 (m = 2^M), often 2³² or 2⁶⁴. The operator denotes a general binary operation. This may be either addition, subtraction, multiplication, or the bitwise arithmetic exclusive-or operator. The theory of this type of generator is rather complex, and it may not be sufficient simply to choose random values for j and k. These generators also tend to be very sensitive to initialisation.

Generators of this type employ k words of state (they 'remember' the last k values).

If the operation used is addition, then the generator is described as an Additive Lagged Fibonacci Generator or ALFG, if multiplication is used, it is a Multiplicative Lagged Fibonacci Generator or MLFG.

Properties of Lagged Fibonacci Generators

Lagged Fibonacci generators have a maximum period of (2^k - 1)*2^M-1 if addition or subtraction is used, and (2^k-1) if exclusive-or operations are used to combine the previous values. If, on the other hand, multiplication is used, the maximum period is (2^k - 1)*2^M-3, or 1/4 of period of the additive case.

For the generator to achieve this maximum period, the polynomial:

y = x^k + x^j + 1

must be primitive over the integers mod 2. Values of j and k satisfying this constraint have been published in the literature. Popular pairs are:

{j = 7, k = 10}, {j = 5, k = 17}, {j = 24, k = 55}, {j = 65, k = 71}, {j = 128, k = 159}, {j = 6, k = 31}, {j = 31, k = 63}, {j = 97, k = 127}, {j = 353, k = 521}, {j = 168, k = 521}, {j = 334, k = 607}, {j = 273, k = 607}, {j = 418, k = 1279}

Another list of possible values for j and k is on page 28 of volume 2 of «The Art of Computer Programming» the values listed above are in bold face:

(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)

Note that the smaller number have short periods (only a few "random" numbers are generated before the first "random" number is repeated and the sequence restarts).

It is required that at least one of the first k values chosen to initialise the generator be odd.

Problems with LFGs

The initialisation of LFGs is a very complex problem. The output of LFGs is very sensitive to initial conditions, and statistical defects may appear initially but also periodically in the output sequence unless extreme care is taken. Another potential problem with LFGs is that the mathematical theory behind them is incomplete, making it necessary to rely on statistical tests rather than theoretical performance. These reasons, combined with the existence of the free and very high-quality Mersenne twister algorithm, tend to make 'home-brewed' implementations of LFGs less than desirable in the presence of superior alternatives.

Пример. Начальные значения: 10, 5, 9, 11, 3.

S_n=S_n-3+S_n-5, m=16, M=4,

максимальный период = (2^k - 1)*2^M-1=31*8=248.

Дата добавления: 2015-07-07