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:

x_{x+1} = (ax_i + b) \ \bmod \ m \,,

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 0 \le x_i < m. 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).

9000 hodnot (3000 bodů) vygenerovaných generátorem RANDU. Je patrné, že body zdaleka nevyplňují celou krychli, ale leží pouze v 15 rovnoběžných rovinách.
9000 hodnot (3000 bodů) vygenerovaných generátorem RANDU. Je patrné, že body zdaleka nevyplňují celou krychli, ale leží pouze v 15 rovnoběžných rovinách.

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