Մասնակից:Dustr.badalyan/Սևագրություն

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

Պետք է նշել որ փոքր թվերը ունեն ավելի փոքր քայլ.Պահանջվում է որ առաջին k արժեքներից մեկը լինի կենտ. j եւ k-ի լավագույն հարաբերությունը նրանց միջին արժեքն է golden ratio.

Խնդիրներ LFGs-ի հետ

Ռոբերտ Զիֆը Robert M. Ziff ասում, որ հայտնի է, որ երկարժեքանի գեներատորների տիպի գեներատորները, ինչպիսին է R(103-250)-ը, ունեն լուրջ թերություններ: Մարսալիան Marsaglia ուսումնասիրել է այդ տիպի գեներատորների վարքը և խորհուրդ է տալիս չօգտագործել այս տիպի գեներատորները.Երկարժեքանի հետադարձ կապով գեներատորների հիմնական թերությունն այն է, որ նրանք կառուցվում են xn, xn − a, և xn − b մեծությունների միջև կոռելյացիայի հիման վրա: Երբ այս գեներատորները տարածվում են գեներատորների չափսերի վրա, դրանք կարող են բերել ակնհայտ էական սխալների. Նախնական արժեքաորումը կարեւոր եւ բարդ խնդիր է LFGs արդյունքը կախված է սկզբնական պայմաններից, սխալներ կարող են պատահել ոչ միայն սկզբնական դեպքում այլ նաև պարբերաբար հաջորդականութան մեջ:Մեկ ուրիշ հնարավոր խնդիրը կապված LFGs-ի հետ այն է, որ մաթեմատիկական տեսությունը անավարտ է, անհրաժեշտ է լինում վստահել ոչ թե փորձերի այլ տեստերի.

Օգտագործված գրականության ցանկ

• 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