Ուշացումով Ֆիբոնաչիի գեներատոր

Վիքիպեդիայից՝ ազատ հանրագիտարանից

Ուշացումով Ֆիբոնաչիի գեներատորը պատահական թվերի գեներատորի օրինակ է։ Այս դասի պատահական թվերի գեներատորը ուղղված է բարելավելու 'ստանդարտ' գծային ներդաշնակ գեներատորները. Սրանք հիմնված են Ֆիբոնաչիի հաջորդականության ընդհանրացման վրա։ Ֆիբոնաչիի հաջորդականությունը կարող է բնութագրվել կրկնվող հարաբերությամբ։

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

Հետևաբար նոր ստացվող թիվը հաջորդականության նախորդ երկու թվերի գումարն է։ Սա ընդհանրացված հաջորդականությունն է։

Որի դեպքում նոր ստացվող թիվը նախորդ երկու թվերի որոշակի կոմբինացիա է. m-ը սովորաբար 2-ի որոշակի աստիճան է։ (m = 2M), հաճախ 232 կամ 264. oպերատորը հիմնականում բինար գործողություն է։ Սա կարող է լինել գումարում, հանում, բազմապատկում կամ էլ բիթային գործողություն թվաբանական բացառիկ-կամ օպերատոր(XOR). Այս տիպի գեներատորների օգտագործման մեխանիզմը բավականին բարդ է, և դժվար է ընտրել j և k-ի համար պատահական թվեր։

Եթե կատարվող գործողությունը գումարում է, ապա գեներատորն անվանում են գումարմամբ ուշացման Ֆիբոնաչիի գեներատոր, եթե բազմապատկում է, ապա բազմապատկմամբ ուշացման Ֆիբոնաչիի գեներատոր, և եթե գործողությունը յուրահատուկ-կամ է XOR, գործողությունն անվանում են երկհնարավոր ընդհանրացված հետադարձ քայլով մուտքագրում: Մերսենի ոլորապտույտ ալգորիթմը երկհնարավոր ընդհանրացված գեներատորի տարատեսակ է։ Վերջինս նման է նաև գծային հետադարձ կապով գեներատորի ալգորիթմին։

Ուշացումով Ֆիբոնաչիի գեներատորի հատկությունները[խմբագրել]

Ուշացումով Ֆիբոնաչիի գեներատորը կատարվում է (2k - 1)*2M-1 անգամ, եթե կատարվող գործողությունը գումարու կամ հանում է, և (2k-1)*k, եթե գործողությունը յուրահատուկ-կամ է։ Մյուս կողմից, եթե կատարվում է բազմապատկում (2k - 1)*2M-3 կամ գումարման 1/4-ը։ Այս մաքսիմում քանակին հասնելու համար անհրաժեշտ բազմանդամի տեսքն է

y = xk + xj + 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}

j և k-ի բոլոր այն հարաբերությունները, որոնք բավարարում են հավասարմանը, անվանում են ոսկե հարաբերություն։

Ուշացումով Ֆիբոնաչիի գեներատորի հետ հնարավոր պրոբլեմները[խմբագրել]

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

Հղումներ[խմբագրել]