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,
$\,a-1$ je dělitelné všemi provočíselnými faktory $\,m$ ,
$\,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

Reference

↑ D. E. Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. str. 17–19.

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

[Knuth-1997-1] D. E. Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. str. 17–19.

[1]