Lineární kongruentní generátor

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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 \le 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]

  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 generátorem RANDU. 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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]

  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.

Externí odkazy[editovat | editovat zdroj]