Lineární kongruentní generátor
Z Wikipedie, otevřené encyklopedie
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, b a m jsou vhodně zvolené konstanty. Počáteční nastavení x0 se nazývá random seed. Tento generátor generuje celá čísla s rovnoměrným rozložením v rozsahu 
. Jelikož počet možných hodnot v tomto rozsahu je omezen, začne se nejpozději po m generovaných číslech opakovat stejná posloupnost (tzv. perioda generátoru).
Větším 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, b, 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, b = 0, m = 231, x0 je liché číslo) používaný okolo roku 1970. (viz en:RANDU)
Příklady konstant:
| zdroj | a | b | m |
|---|---|---|---|
| Numerical Recipes | 1 664 525 | 1 013 904 223 | 232 |
| RAND | 69 069 | 1 | 232 |
| VAX ANSI C | 1 103 515 245 | 12 345 | 231 |
| Park & Miller | 16 807 | 0 | 231 − 1 |
[editovat] Příklad v C
unsigned int x, a, b;
void Reset()
{
x = 0; // Random seed (náhodné semínko)
a = 69069;
b = 1;
}
unsigned int GenerateNext()
{
x = x*a + b;
return x;
}
[editovat] Podívejte se také na
[editovat] 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
