Kombinerad linjär kongruentialgenerator

En kombinerad linjär kongruentialgenerator ( CLCG ) är en pseudo-slumptalsgeneratoralgoritm baserad på att kombinera två eller flera linjära kongruentialgeneratorer (LCG). En traditionell LCG har en period som är otillräcklig för komplex systemsimulering. Genom att kombinera två eller flera LCG kan slumptal med längre period och bättre statistiska egenskaper skapas. Algoritmen definieras som:

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

var:

$m_{1}$ är " modulen " för den första LCG

$Y_{i,j}$ är den i: ^te ingången från den j ^:te LCG

$X_{ i}$ är det i: te ^genererade slumpmässiga heltal

med:

$R_{i}\equiv {\begin{cases}X_{i}/m_{1} &{\text{för }}X_{i}>0\\(m_{1}-1)/m_{1}&{\text{för }}X_{i}=0\end{fall}}$

där $R_{i}$ är ett likformigt fördelat slumptal mellan 0 och 1.

Härledning

Om W _{i ,1} , W _{i ,2} , ..., W _{i ,k} är vilka som helst oberoende, diskreta, slumpmässiga variabler och en av dem är likformigt fördelad från 0 till m ₁ − 2, så är Z _i likformigt fördelad mellan 0 och m ₁ − 2, där:

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

Låt Xi _{,1 ,} Xi , _{2 ,} ..., _{Xi k vara} , utsignaler från k LCG. Om W _{i , j} definieras som X _{i , j} − 1, så kommer Wi _{, j en} att vara ungefär likformigt fördelade från 0 till m _j − 1. Koefficienten "(−1) ^{j −1} " utför implicit subtraktionen av från Xi _{_ , j} .

Egenskaper

CLCG ger ett effektivt sätt att beräkna pseudoslumptal. LCG-algoritmen är beräkningsmässigt billig att använda. Resultaten av flera LCG-algoritmer kombineras genom CLCG-algoritmen för att skapa pseudoslumptal med en längre period än vad som är möjligt med LCG-metoden i sig.

Perioden för en CLCG är den minsta gemensamma multipeln av perioderna för de individuella generatorerna, som är en mindre än modulerna. Eftersom alla moduler är udda primtal är perioderna jämna och delar därför åtminstone en gemensam divisor på 2, men om modulerna väljs så att 2 är den största gemensamma delaren för varje par, kommer detta att resultera i en period av :

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

Exempel

Följande är ett exempel på en algoritm utformad för användning i 32-bitars datorer:

$k=2$

LCG används med följande egenskaper:

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

CLCG-algoritmen är inställd enligt följande:

1. Fröet för den första LCG, $Y_{0,1}$ , bör väljas inom området [1, 2147483562].

Fröet för den andra LCG, $Y_{0,2}$ , bör väljas i intervallet [1, 2147483398].

Set: $i=0$

2. De två LCG:erna utvärderas enligt följande:

$Y_{i+1,1}=40014\times Y_{i,1}{\pmod {2147483563}}$

$Y_{i+1,2}=40692\times Y_{i,2}{\pmod {2147483399}}$

3. CLCG-ekvationen löses enligt nedan:

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

4. Beräkna slumptalet:

${\+displaystyle R_ 1}={\begin{cases}X_{i+1}/2147483563&{\text{för }}X_{i+1}>0\\(X_{i+1}/2147483563)+1&{\text{ för }}X_{i+1}<0\\2147483562/2147483563&{\text{för }}X_{i+1}=0\end{fall}}}$

5. Öka räknaren ( i = i + 1) och återgå sedan till steg 2 och upprepa.

Den maximala perioden för de två LCG som används beräknas med formeln:.

$(m-1)$

Detta motsvarar 2,1×10 ⁹ för de två LCG som används.

Denna CLCG som visas i det här exemplet har en maximal period på:

$(m_{1}-1)(m_{2}-1)/2\approx 2.3\times 10^{18}$

Detta representerar en enorm förbättring under perioden för de individuella LCG:erna. Det kan ses att den kombinerade metoden ökar perioden med 9 storleksordningar.

Överraskande nog är perioden för denna CLCG kanske inte tillräcklig för alla applikationer. Andra algoritmer som använder CLCG-metoden har använts för att skapa pseudoslumptalsgeneratorer med perioder så långa som 3×10 ⁵⁷ .

Se även

• Linjär kongruentialgenerator
• Wichmann–Hill , en specifik kombinerad LCG som föreslogs 1982

externa länkar

• En översikt över användning och testning av pseudo-slumptalsgeneratorer