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 = ( a x i + c )   mod   m {\displaystyle x_{i+1}=(ax_{i}+c)\ {\bmod {\ }}m\,} ,

kde operace mod znamená zbytek po celočíselném dělení, a {\displaystyle a} , c {\displaystyle c} a m {\displaystyle m} jsou vhodně zvolené konstanty. Počáteční nastavení x 0 {\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 0 ≤ x i < m {\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 m {\displaystyle m} vygenerovaných číslech opakovat stejná posloupnost (tzv. perioda generátoru). Generátor bude mít plnou periodu ( m {\displaystyle m} ) právě tehdy, když:[1]

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

Příklady konstant:

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

Reference

  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

  • 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