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:
- ,
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ž:[1]
- a jsou nesoudělná čísla,
- je dělitelné všemi provočíselnými faktory ,
- je násobek 4, jestliže je násobek 4.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/0f/Randu2.png/220px-Randu2.png)
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
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