Lagged Fibonacci generator

'Lagged Fibonacci-ի գեներատորը (LFG)պատահական կեղծ թվերի գեներատորի pseudorandom number generator օրինակ է . Այն նպատակն ունի բարելավել որպես 'ստանդարտ' գծային գեներատորlinear congruential generator.Սրանք հիմնված են Ֆիբոնաչիի հաջորդականության ընդհանրացման վրա Fibonacci sequence. Fibonacci-ի հաջորդականությունը կարելի է ներկայացնել հարաբերեւթյունների կրկնության recurrence relation ձեւով:

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

Այսպիսով , նոր արժեքը դա հաջորդ 2 թվերի գումարն է հաջորդականության մեջ.Սա ընդհանրացված հաջորդականությունն է.

$S_{n}\equiv S_{n-j}\star S_{n-k}{\pmod {m}},0<j<k$

Այսպիսով յուրաքանչուր նոր արժեք ստացվում է նախորդ երկու արժեքների գումարից.M թիիվը սովորաբար 2-ի աստիճան է (m = 2^M), հաճախ 2³² or 2^{64</sup: $\star$ գեներատորը ցույց է տալիս ընդհանուր binary-ի գործողությունն է binary operation. Դրանք կարող են լինել գումարում,հանում,բազմապատիկում կամ բիթվայզ bitwise գործողությունները: Այս տեսակի գեներատորի տեսությունը բավականին բարդ է եւ հնարավոր է որ բավարար չլինեի միայն j եւ k թվերի ընտրությունը.Այս գեներատորները սկզբնական արժեքի նկատմամբ բավականին զգայուն են. Այս տեսակի գեներատորները օգտագործում են k թվեր. Եթե օգտագործվում է գումարման գործողությունը այդ դեպքում գեներատորը անվանում ենքAdditive Lagged Fibonacci Generator կամ ALFG,եթե օգտագործվում է բազմապատկման գործողությունը ապա այն անվանում ենք Multiplicative Lagged Fibonacci Generator կամ MLFG եւ եթե օգտագործվում է XOR գործողությունը եւ այն անվանում ենք Two-tap generalised feedback shift register կամ GFSR.: Mersenne twister ալգորիթմը GFSR-ի փոփոխված տարբերակներից մեկն է: GFSR-ն կապված է նաեւ Linear Feedback Shift Register-ից.}

lagged Fibonacci-ի գեներատորի հատկությունները

Lagged Fibonacci գեներատորը ունի առավելագույնը (2^k - 1)*2^M-1 քայլ եթե օգտագործված է գումարում , հանում եւ 2^k-1)*k,եւ եթե օգտագործվում է XOR գործողությունը միավորելու նախորդ արժեքները.Մյուս կողմից եթե բազմապատկում ենք օգտագործում ամենամեծ քայլը (2^k - 1)*2^M-3 է կամ գումարման դեպքի 1/4-ը. Որպեսզի հաշվենք ամենամեծ քայլը օգտագործում ենք հետեւյալ բազմանդամը.

y = x^k + x^j + 1

j և k-ի այս հավասարմանը բավարարող արժեքներից ամենաճանաչվածներն են.

{j = 7, k = 10}, {j = 5, k = 17}, {j = 24, k = 55}, {j = 65, k = 71}, {j = 128, k = 159} [1], {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} [2]

j եւk մեկ ուրիշ հնարավոր արժեքներ ներկայացված են of The Art of Computer Programming գրքի 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)

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.

It has been suggested that good ratios between j and k are approximately the golden ratio.

Problems with LFGs

In a paper on four-tap shift registers, Robert M. Ziff, referring to LFGs that use the XOR operator, states that "It is now widely known that such generators, in particular with the two-tap rules such as R(103, 250), have serious deficiencies. Marsaglia observed very poor behavior with R(24,55) and smaller generators, and advised against using generators of this type altogether. ... The basic problem of two-tap generators R(a, b) is that they have a built-in three-point correlation between $x_{n}$, $x_{n-a}$, and $x_{n-b}$, simply given by the generator itself ... While these correlations are spread over the size $p=max(a,b,c,\ldots )$ of the generator itself, they can evidently still lead to significant errors.". This only refers to the standard LFG where each new number in the sequence depends on two previous numbers. A three-tap LFG has been shown to eliminate some statistical problems such as failing the Birthday Spacings and Generalized Triple tests.

The initialization 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.

Usage

• Freeciv uses a lagged Fibonacci generator with {j = 24, k = 55} for its random number generator.
• The Boost library includes an implementation of a lagged Fibonacci generator.
• Subtract with carry, a lagged Fibonacci generator engine, is included in the C++11 library.
• The Oracle Database implements this generator in its DBMS_RANDOM package (available in Oracle 8 and newer versions).
• The "Pocket Dungeon" on www.BoardGameGeek.com uses it as an alternative 'Stealth' dice roll generator.

See also

• Linear congruential generator
• Mersenne twister
• FISH (cipher)
• Pike
• VIC cipher