Lineární kongruentní generátor

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: :x_{i+1} = (ax_i + c) \ \bmod \ m \,, kde operace mod znamená zbytek po celočíselném dělení, a, c a m jsou vhodně zvolené konstanty. Počáteční nastavení x_0 se nazývá random seed („náhodné semínko“). +more Generátor generuje celá čísla s rovnoměrným rozložením v rozsahu 0 \le x_i . Poněvadž je počet možných hodnot v tomto rozsahu omezen, začne se nejpozději po m vygenerovaných číslech opakovat stejná posloupnost (tzv. perioda generátoru). Generátor bude mít plnou periodu (m) právě tehdy, když: # \,c a \,m jsou nesoudělná čísla, # \,a - 1 je dělitelné všemi provočíselnými faktory \,m, # \,a - 1 je násobek 4, jestliže \,m je násobek 4.

9000 hodnot (3000 bodů) vygenerovaných lineárním konguentním generátorem při špatně zvolených konstantách a, c, m. +more 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 a, c, 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, c=0, m=2^{31}, x_0 je liché číslo) používaný okolo roku 1970.

Příklady konstant:

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

[url=://tjn.fjfi.cvut.cz/~virius/prednes/mc-prikl/Randu.html

[[Kategorie:Generátory pseudonáhodných čísel]url=http://cer. freeshell. +moreorg/renma/LibraryRandomNumber/]Zdrojové kódy LCG v různých programovacích jazycích[/url] * Test generátoru pseudonáhodných čísel RANDU:[/url]].