Lineární kongruentní generátor

Z Wikipedie, otevřené encyklopedie

Lineární kongruentní generátor (anglicky Linear Congruential Generator, zkratka LCG) je jeden z nejstarších a nejjednodušších generátorů pseudonáhodných čísel.

Je definován vztahem:

$x_{i+1} = (ax_i + b) \ \bmod \ m \,$ ,

kde operace mod znamená zbytek po celočíselném dělení, $a$ , $b$ a $m$ jsou vhodně zvolené konstanty. Počáteční nastavení $x 0$ se nazývá random seed. Tento generátor generuje celá čísla s rovnoměrným rozložením v rozsahu $0 \le x_i < m$ . Jelikož počet možných hodnot v tomto rozsahu je omezen, začne se nejpozději po $m$ generovaných číslech opakovat stejná posloupnost (tzv. perioda generátoru).

9000 hodnot (3000 bodů) vygenerovaných generátorem RANDU. Je patrné, že body zdaleka nevyplňují celou krychli, ale leží pouze v 15 rovnoběžných rovinách.

Větším problém, než je periodicita generátoru, lze u tohoto typu generátoru pozorovat při generování náhodných bodů v prostoru. V případě špatně zvolených hodnot $a$ , $b$ , $m$ leží vygenerované body v několika rovnoběžných rovinách, zatímco zbytek prostoru, který by měl být rovnoměrně zaplněn, je prázdný. Nechvalně se tak proslavil například generátor RANDU ( $a = 65539$ , $b = 0$ , $m = 2 31$ , $x 0$ je liché číslo) používaný okolo roku 1970. (viz en:RANDU)

Příklady konstant:

zdroj	a	b	m
Numerical Recipes	1 664 525	1 013 904 223	$232$
RAND	69 069	1	$232$
VAX ANSI C	1 103 515 245	12 345	$231$
Park & Miller	16 807	0	$231 - 1$

[editovat] Příklad v C

unsigned int x, a, b;
 
void Reset()
{
        x = 0;      // Random seed (náhodné semínko)
        a = 69069;
        b = 1;
}
 
unsigned int GenerateNext()
{
        x = x*a + b;
        return x;
}