Lineární kongruentní generátor

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:

${\displaystyle x_{i+1}=(ax_{i}+c)\ {\bmod {\ }}m\,}$,

kde operace mod znamená zbytek po celočíselném dělení, ${\displaystyle a}$, ${\displaystyle c}$ a ${\displaystyle m}$ jsou vhodně zvolené konstanty. Počáteční nastavení ${\displaystyle x_{0}}$ se nazývá random seed („náhodné semínko“). Generátor generuje celá čísla s rovnoměrným rozložením v rozsahu ${\displaystyle 0\leq x_{i}<m}$. Poněvadž je počet možných hodnot v tomto rozsahu omezen, začne se nejpozději po ${\displaystyle m}$ vygenerovaných číslech opakovat stejná posloupnost (tzv. perioda generátoru). Generátor bude mít plnou periodu (${\displaystyle m}$) právě tehdy, když:^[1]

1. ${\displaystyle \,c}$ a ${\displaystyle \,m}$ jsou nesoudělná čísla,
2. ${\displaystyle \,a-1}$ je dělitelné všemi provočíselnými faktory ${\displaystyle \,m}$,
3. ${\displaystyle \,a-1}$ je násobek 4, jestliže ${\displaystyle \,m}$ je násobek 4.

9000 hodnot (3000 bodů) vygenerovaných lineárním konguentním generátorem při špatně zvolených konstantách a, c, m. Je patrné, že body zdaleka nevyplňují celou krychli, ale leží pouze v 15 rovnoběžných rovinách.

Větší 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 ${\displaystyle a}$, ${\displaystyle c}$, ${\displaystyle 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 (${\displaystyle a=65539}$, ${\displaystyle c=0}$, ${\displaystyle m=2^{31}}$, ${\displaystyle x_{0}}$ je liché číslo) používaný okolo roku 1970.

Příklady konstant:

Příklad v C

unsigned int x, a, c;

void Reset()
{
	x = 0; // Random seed (náhodné semínko)
	a = 69069;
	c = 1;
}

unsigned int GenerateNext()
{
	x = x*a + c;
	return x;
}

Související články

• Generátor pseudonáhodných čísel

Reference

Externí odkazy

• Zdrojové kódy LCG v různých programovacích jazycích
• Test generátoru pseudonáhodných čísel RANDU: http://tjn.fjfi.cvut.cz/~virius/prednes/mc-prikl/Randu.html