Գծային համընկման գեներատոր

Գծային համընկման գեներատոր —ալգորիթմներից մեկը` կեղծ պատահական թվերի գեներատորը, օգտագործվում է սովորական դեպքերում:

Նկարագրություն

Գծային համընկման գեներատորը հիմնվում է անդամների հաշվարկման գծային հետևողականությամբ որոշ բնական թվի m մոդուլով, հետևյալ ֆորմուլայի տեսքով:

$X_{k+1} = (a X_k + c)~~\bmod~~m,$

որտեղ a և c-ն որոշ ամբողջ թվերի կոէֆիցիենտներ են: Ստացված հետևողականությունը կախված է մեկնարկային թվի ընտրությունից X0 և նրա տարբեր նշանակությունների դեպքում ստացվում է պատահական թվերի տարբեր արդյունք: Միաժամանակ այս արդյունքների շատ հատկություններ որոշվում են ֆորմուլայի կոէֆիցենտների ընտրությամբ և կախված չեն մեկնարկային թվերի ընտրությունից:

Հատկություն

Թվերի հետևողականությունը, որը ստացվում է գծային համընկման մեթոդով, պարբերաբար չգերազանցվողm է: Հատվածի երկարությունը ճիշտ հավասար է m միայն այն դեպքում, երբ:

1. 1. Ամենամեծ ընդհանուր բաժանարար, այսինքն`c, m = 1 փոխադարձ հասարակ թվեր;
2. 2. a-1 բոլոր հասարակ թվի բաժանարար  ;

Ստացված արդյունքի պատահական թվերի վիճակագրական հատկությունները ամբողջովին որոշվում են a և c կոէֆիցենտների ընտրությամբ: Այս հաստատունների համար դուրս են գրված պայմաններ, որոնք երաշխավորում են ստացված պատահական թվերի բավարար որակ:

Հաճախ օգտագործվող պարամետրեր

Իրացման ժամանակ ճիշտ է ընտրել $m = 2^e$, որտեղ e — որտեղ e բիտերի քանակը, քանի որ դա թույլ է տալիս ազատվել համեմատաբար դանդաղ հետազոտություններից:

Փոքր երկրորդական կարգի գեներացված պատահական թվերը ցուցադրում են վարմունք, որը շատ հեռու է պատահականից, դրա համար խորհուրդ է տրվում օգտագործել միայն բարձր կարգեր: Բացի դրանից այս գեներատորի օգտագործման ժամանակ կետերի ընտրման համար d-տարածությունում, կետերն ընկնում են ոչ ավել գիպերհարթություններում, $m^{1/d}$ , ինչը սահմանափակում է m1 / d գեներատորի կիրառումը Մոնթե-Կառլի մեթոդով:

Աղյուսակում բերված են առավել հաճախ օգտագործվող գծային համընկման գեներատորների պարամետրերը, հատկապես տարբեր կազմված միօրինակ գրադարաններում:

Աղյուսակ	m	a	c	թողարկված բիտերի արդյունք
Numerical Recipes	232	1664525	1013904223
Borland C/C++	232	22695477	1	բիտ 30..16 в
GNU Compiler Collection	232	69069	5	բիտ 30..16
ANSI C: Open Watcom, Digital Mars, Metrowerks, IBM VisualAge C/C++	232	1103515245	12345	բիտ 30..16
Borland Delphi, Virtual Pascal	232	134775813	1	բիտ63..32
Microsoft Visual/Quick C/C++	232	214013	2531011	բիտ30..16
Apple CarbonLib	231 - 1	16807	0	см. Կաղապար:Не переведено

Ծածկագրերի վերլուծություն

Գծային մեթոդի առավելությունը կայանում է նրանում, որ գործոնը և մոդուլը համապատասխան ձևով ընտրվում են, ապա ստեղծված թվերի արդյունքը կլինի վիճակագրապես անտարբերելի պատահական արդյունքների բազմաթիվ էլեմենտներից: { 0, 1, 2, …, m-1 }. Սակայն բոլոր արդյունքային այն էլեմենտները միանշանակ որոշվում են 4 պարամետրերով` X_0, a, c, m.

Եթե ծածկագրերի վերլուծությունը գիտի հայտնի պարամետրերով գծային համընկման մեթոդի օգտագործումը, ապա հայտնի է դառնում թվերի ամբողջ արդյունքը: Միաժամանակ, անգամ եթե ծածկագրությունը գիտի միայն գծային համընկամն մեթոդի օգտագործումը, ապա արդյունքի փոքր հատվածի տեղեկատվությունը բավական է մեթոդի պարամետրերի և արդյունքների բոլոր հաջորդող էլեմենտների հայտնաբերումը:Մասնավորապես, եթե ծածկագրերի վերլուծությանը հայտնի են նշանակությունները ${X_0}, {X_1}, {X_2}, {X_3}$, ապա նրանք բավարարում են հավասարության համակարգին:

$\begin{cases} X_{1} = (a\cdot X_{0} + c )~ \bmod~ m\\ X_{2} = (a\cdot X_{1} + c )~ \bmod~ m\\ X_{3} = (a\cdot X_{2} + c )~ \bmod~ m\end{cases}$

որից կարելի է ստանալ а, с и m.

Դրա համար, թեև գծային համընկման մեթոդը տալիս է վիճակագրապես լավ թվերի արդյունք, նա չի համարվում ծածկագրության դիմացկուն:

Հղումներ

• Կաղապար:Հեղինակ=Լ. Բառաշ
• Ս. Գաշկո "Պատահական գեներատորների համարները"
• Случайные числа : программная реализация