Ուշացումով Ֆիբոնաչիի գեներատոր
Ուշացումով Ֆիբոնաչիի գեներատորը պատահական թվերի գեներատորի օրինակ է: Այս դասի պատահական թվերի գեներատորը ուղղված է բարելավելու 'ստանդարտ' գծային ներդաշնակ գեներատորները. Սրանք հիմնված են Ֆիբոնաչիի հաջորդականության ընդհանրացման վրա: Ֆիբոնաչիի հաջորդականությունը կարող է բնութագրվել կրկնվող հարաբերությամբ:
Հետևաբար նոր ստացվող թիվը հաջորդականության նախորդ երկու թվերի գումարն է: Սա ընդհանրացված հաջորդականությունն է:
Որի դեպքում նոր ստացվող թիվը նախորդ երկու թվերի որոշակի կոմբինացիա է. 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 մեծությունների միջև կոռելյացիայի հիման վրա: Երբ այս գեներատորները տարածվում են գեներատորների չափսերի վրա, դրանք կարող են բերել ակնհայտ էական սխալների: Ուշացումով Ֆիբոնաչիի գեներատորի կարգաբերումը բարդ, համալիր խնդիր է: Այս գեներատորի մեկ այլ պոտենցիալ պրոբլեմ է այն, որ դրան վերաբերող մաթեմատիկական տեսությունն ամբողջական չէ, և այդ պատճառով ավելի շատ հաշվի են առնվում վիճակագրական դիտարկումներն ու հետազոտությունները, քան տեսական գաղափարները:
