Lineární kongruentní generátor (anglicky , zkratka LCG) je jeden z nejstarších a nejjednodušších generátorů pseudonáhodných čísel.
Je definován vztahem: , kde operace mod znamená zbytek po celočíselném dělení, , a jsou vhodně zvolené konstanty. Počáteční nastavení se nazývá random seed („náhodné semínko“). Generátor generuje celá čísla s rovnoměrným rozložením v rozsahu . Poněvadž je počet možných hodnot v tomto rozsahu omezen, začne se nejpozději po vygenerovaných číslech opakovat stejná posloupnost (tzv. perioda generátoru). Generátor bude mít plnou periodu () právě tehdy, když:D. E. Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. . str. 17–19. a jsou nesoudělná čísla, je dělitelné všemi provočíselnými faktory , je násobek 4, jestliže je násobek 4.
náhled|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 , , 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 (, , , je liché číslo) používaný okolo roku 1970.
Příklady konstant: zdroj m a c výstup Numerical Recipes 1 664 525 1 013 904 223 Borland C/C++ 22 695 477 1 bity 30–16 v rand(), 30–0 v lrand() glibc (GCC) 1 103 515 245 12 345 bity 30–0 ANSI C: Watcom, Digital Mars, CodeWarrior, IBM VisualAge C/C++ 1 103 515 245 12 345 bity 30–16 Borland Delphi, Virtual Pascal 134 775 813 1 bity 63–32 ze (seed * L) Microsoft Visual/Quick C/C++ 214 013 2 531 011 bity 30–16 Apple CarbonLib (Park & Miller) 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
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
Kategorie:Generátory pseudonáhodných čísel