Біріктірілген сызықтық конгруденциялы генератор - Combined linear congruential generator

A біріктірілген сызықтық конгруденциялы генератор (CLCG) Бұл жалған кездейсоқ сан генераторы алгоритм екі немесе одан көп біріктіруге негізделген сызықтық конгруденциялы генераторлар (LCG). Дәстүрлі LCG а кезең бұл жүйені күрделі модельдеу үшін жеткіліксіз.^[1] Екі немесе одан да көп LCG-ді біріктіру арқылы кезеңі ұзағырақ және статистикалық қасиеттері жақсы кездейсоқ сандар жасауға болады.^[1]Алгоритм келесідей анықталады:^[2]

${ displaystyle X_ {i} equiv left ( sum _ {j = 1} ^ {k} (- 1) ^ {j-1} Y_ {i, j} right) { pmod {m_ {1 } -1}}}$

қайда:

${ displaystyle m_ {1}}$ бұл «модуль «бірінші LCG

${ displaystyle Y_ {i, j}}$ болып табылады мен^мың ішінен кіріс j^мың LCG

${ displaystyle X_ {i}}$ болып табылады мен^мың кездейсоқ бүтін сан

бірге:

${ displaystyle R_ {i} equiv { begin {case} X_ {i} / m_ {1} & { text {for}} X_ {i}> 0 (m_ {1} -1) / m_ {1} & { text {for}} X_ {i} = 0 end {case}}}$

қайда ${ displaystyle R_ {i}}$ Бұл біркелкі бөлінген 0 мен 1 арасындағы кездейсоқ сан.

Шығу

Егер W_мен,1, W_мен,2, ..., W_{мен, к} кез келген тәуелсіз, дискретті, кездейсоқ-айнымалылар және олардың біреуі 0-ден біркелкі үлестірілген м₁ - 2, содан кейін З_мен 0 мен аралығында біркелкі бөлінеді м₁ - 2, мұнда:^[2]

${ displaystyle Z_ {i} = солға ( sum _ {j = 1} ^ {k} W_ {i, j} right) { pmod {m_ {1} -1}}}$

Келіңіздер X_мен,1, X_мен,2, ..., X_мен,к шығу болуы керек к LCG. Егер W_мен,j ретінде анықталады X_мен,j - 1, содан кейін W_мен,j 0-ден шамамен біркелкі бөлінеді м_j − 1.^[2] Коэффициент «(−1)^j−1«біреуін алып тастауды жасырын түрде орындайды X_мен,j.^[1]

Қасиеттері

CLCG жалған кездейсоқ сандарды есептеудің тиімді әдісін ұсынады. LCG алгоритмін пайдалану есептеу үшін арзан.^[3] Бірнеше LCG алгоритмдерінің нәтижелері CLCG алгоритмі арқылы ұзағырақ жалған кездейсоқ сандарды құру үшін біріктіріледі кезең LCG әдісімен өздігінен қол жеткізуге болады.^[3]

CLCG кезеңі болып табылады ең кіші ортақ еселік модульдерден бір кем жеке генераторлардың периодтары. Барлық модульдер тақ қарапайым болғандықтан, периодтар жұп болады және осылайша, кем дегенде, 2-дің ортақ бөлгішін бөледі, бірақ егер модульдер таңдалса, 2 ең үлкен ортақ бөлгіш әр жұптың нәтижесі:^[1]

${ displaystyle P = { frac {(m_ {1} -1) (m_ {2} -1) cdots (m_ {k} -1)} {2 ^ {k-1}}}}$

Мысал

Төменде 32 биттік компьютерлерде қолдануға арналған алгоритмнің мысалы келтірілген:^[2]

${ displaystyle k = 2}$

LCG келесі қасиеттермен қолданылады:

${ displaystyle { begin {aligned} a_ {1} & = 40014 & a_ {2} & = 40692 m_ {1} & = 2147483563 & m_ {2} & = 2147483399 c_ {1} & = 0 & c_ {2} & = 0 end {aligned}}}$

CLCG алгоритмі келесідей орнатылған:

1. Бірінші LCG тұқымы, ${ displaystyle Y_ {0,1}}$, [1, 2147483562] аралығында таңдау керек.

Екінші LCG тұқымы, ${ displaystyle Y_ {0,2}}$, [1, 2147483398] аралығында таңдау керек.

Жинақ: ${ displaystyle i = 0}$

2. Екі LCG төмендегідей бағаланады:

${ displaystyle Y_ {i + 1,1} = 40014 рет Y_ {i, 1} { pmod {2147483563}}}$

${ displaystyle Y_ {i + 1,2} = 40692 рет Y_ {i, 2} { pmod {2147483399}}}$

3. CLCG теңдеуі төменде көрсетілгендей шешіледі:

${ displaystyle X_ {i + 1} = (Y_ {i + 1,1} -Y_ {i + 1,2}) { pmod {2147483563}}}$

4. Кездейсоқ санды есептеңіз:

${ displaystyle R_ {i + 1} = { begin {case} X_ {i + 1} / 2147483563 & { text {for}} X_ {i + 1}> 0 (X_ {i + 1} / 2147483563) ) +1 & { text {for}} X_ {i + 1} <0 2147483562/2147483563/ & { text {for}} X_ {i + 1} = 0 end {case}}}$

5. Есептегішті көбейтіңіз (мен = мен + 1) содан кейін 2-қадамға оралып, қайталаңыз.

Қолданылған екі LCG максималды кезеңі мына формула бойынша есептеледі :.^[1]

${ displaystyle (m-1)}$

Бұл 2,1 × 10-ға тең⁹ пайдаланылған екі LCG үшін.

Осы мысалда көрсетілген CLCG максималды кезеңіне ие:

${ displaystyle (m_ {1} -1) (m_ {2} -1) / 2 шамамен 2.3 рет 10 ^ {18}}$

Бұл жеке LCG кезеңінде айтарлықтай жақсаруды білдіреді. Біріктірілген әдіс периодты 9 дәрежеге арттыратынын көруге болады.

Таңқаларлықтай, осы CLCG мерзімі барлық қосымшалар үшін жеткіліксіз болуы мүмкін.^[1] CLCG әдісін қолданатын басқа алгоритмдер периодтары 3 × 10 дейінгі псевдо-кездейсоқ сандар генераторларын құруда қолданылған.⁵⁷.^[4][5][6]

Сондай-ақ қараңыз

• Сызықтық конгруденциялы генератор
• Вичманн-Хилл, 1982 жылы ұсынылған нақты аралас LCG

Әдебиеттер тізімі

Сыртқы сілтемелер

• Псевдо-кездейсоқ сандардың генераторларын қолдану мен тестілеуге шолу