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