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, b a m jsou vhodně zvolené konstanty. Počáteční nastavení x₀ 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).

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 = 2³¹, x₀ je liché číslo) používaný okolo roku 1970. (viz en:RANDU)

Příklady konstant:

[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] Související články

• Generátor pseudonáhodných čísel

[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