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:

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

kde operace mod znamená zbytek po celočíselném dělení, $a$, $c$ a $m$ jsou vhodně zvolené konstanty. Počáteční nastavení $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 $0\leq x_{i}<m$. Poněvadž je počet možných hodnot v tomto rozsahu omezen, začne se nejpozději po $m$ vygenerovaných číslech opakovat stejná posloupnost (tzv. perioda generátoru). Generátor bude mít plnou periodu ($m$) právě tehdy, když:

1. $\,c$ a $\,m$ jsou nesoudělná čísla,
2. $\,a-1$ je dělitelné všemi provočíselnými faktory $\,m$,
3. $\,a-1$ je násobek 4, jestliže $\,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 $a$, $c$, $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$, $c=0$, $m=2^{31}$, $x_{0}$ je liché číslo) používaný okolo roku 1970.

Příklady konstant:

zdroj	m	a	c	výstup
Numerical Recipes	$2^{32}$	1 664 525	1 013 904 223
Borland C/C++	$2^{32}$	22 695 477	1	bity 30–16 v rand(), 30–0 v lrand()
glibc (GCC)	$2^{32}$	1 103 515 245	12 345	bity 30–0
ANSI C: Watcom, Digital Mars, CodeWarrior, IBM VisualAge C/C++	$2^{32}$	1 103 515 245	12 345	bity 30–16
Borland Delphi, Virtual Pascal	$2^{32}$	134 775 813	1	bity 63–32 ze (seed * L)
Microsoft Visual/Quick C/C++	$2^{32}$	214 013	2 531 011	bity 30–16
Apple CarbonLib (Park & Miller)	$2^{32}-1$	16 807	0

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

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