Kombinovaný lineární shodný generátor - Combined linear congruential generator

A kombinovaný lineární shodný generátor (CLCG) je pseudonáhodné generátor čísel algoritmus na základě kombinace dvou nebo více lineární shodné generátory (LCG). Tradiční LCG má a doba což je nedostatečné pro komplexní simulaci systému.^[1] Kombinací dvou nebo více LCG lze vytvořit náhodná čísla s delší periodou a lepšími statistickými vlastnostmi.^[1]Algoritmus je definován jako:^[2]

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

kde:

${ displaystyle m_ {1}}$ je "modul "prvního LCG

${ displaystyle Y_ {i, j}}$ je i^th vstup z j^th LCG

${ displaystyle X_ {i}}$ je i^th generované náhodné celé číslo

s:

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

kde ${ displaystyle R_ {i}}$ je rovnoměrně rozloženo náhodné číslo mezi 0 a 1.

Derivace

Li Ž_i,1, Ž_i,2, ..., Ž_{i, k} jsou jakékoli nezávislé, diskrétní, náhodné proměnné a jedna z nich je rovnoměrně rozložena od 0 do m₁ - 2 tedy Z_i je rovnoměrně rozloženo mezi 0 a m₁ - 2, kde:^[2]

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

Nechat X_i,1, X_i,2, ..., X_i,k být výstupy z k LCG. Li Ž_i,j je definován jako X_i,j - 1 tedy Ž_i,j bude přibližně rovnoměrně rozloženo od 0 do m_j − 1.^[2] Koeficient "(-1)^j−1"implicitně provádí odečtení jednoho z X_i,j.^[1]

Vlastnosti

CLCG poskytuje efektivní způsob výpočtu pseudonáhodných čísel. Algoritmus LCG je výpočetně nenáročný na použití.^[3] Výsledky více algoritmů LCG jsou kombinovány pomocí algoritmu CLCG a vytvářejí pseudonáhodná čísla s delší doba než je samo o sobě dosažitelné metodou LCG.^[3]

Období CLCG je nejmenší společný násobek period jednotlivých generátorů, které jsou o jednu menší než moduly. Vzhledem k tomu, že všechny moduly jsou lichá prvočísla, jsou periody sudé a sdílejí tedy alespoň společného dělitele 2, ale pokud jsou moduly zvoleny tak, že 2 je největší společný dělitel každého páru to povede k období:^[1]

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

Příklad

Následuje ukázkový algoritmus navržený pro použití ve 32bitových počítačích:^[2]

${ displaystyle k = 2}$

LCG se používají s následujícími vlastnostmi:

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

Algoritmus CLCG je nastaven následovně:

1. Semeno pro první LCG, ${ displaystyle Y_ {0,1}}$, by měl být vybrán v rozsahu [1, 2147483562].

Semeno pro druhý LCG, ${ displaystyle Y_ {0,2}}$, by měl být vybrán v rozsahu [1, 2147483398].

Soubor: ${ displaystyle i = 0}$

2. Dvě LCG se hodnotí následovně:

${ displaystyle Y_ {i + 1,1} = 40014 krát Y_ {i, 1} { pmod {2147483563}}}$

${ displaystyle Y_ {i + 1,2} = 40692 krát Y_ {i, 2} { pmod {2147483399}}}$

3. Rovnice CLCG je řešena tak, jak je uvedeno níže:

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

4. Vypočítejte náhodné číslo:

${ displaystyle R_ {i + 1} = { begin {cases} 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 {případů}}}$

5. Zvyšte počítadlo (i = i + 1), poté se vraťte ke kroku 2 a opakujte.

Maximální doba dvou použitých LCG se vypočítá podle vzorce :.^[1]

${ displaystyle (m-1)}$

To odpovídá 2,1 × 10⁹ pro dva použité LCG.

Tento CLCG zobrazený v tomto příkladu má maximální dobu:

${ displaystyle (m_ {1} -1) (m_ {2} -1) / 2 přibližně 2,3 krát 10 ^ {18}}$

To představuje obrovské zlepšení v období jednotlivých LCG. Je vidět, že kombinovaná metoda zvyšuje periodu o 9 řádů.

Překvapivě období tohoto CLCG nemusí být dostatečné pro všechny aplikace.^[1] Jiné algoritmy využívající metodu CLCG byly použity k vytvoření generátorů pseudonáhodných čísel s periodami tak dlouho, jak 3 × 10⁵⁷.^[4][5][6]

Viz také

• Lineární kongruentní generátor
• Wichmann – Hill, specifická kombinovaná LCG navržená v roce 1982

Reference

externí odkazy

• Přehled použití a testování generátorů pseudonáhodných čísel