Lehmerův generátor pseudonáhodných čísel

Lehmerův generátor pseudonáhodných čísel neboli Parkův-Millerův generátor pseudonáhodných čísel je typ lineárního kongruentního generátoru, který počítá v multiplikativní grupě modulo n. Obecný rekurentní vzorec pro prvky jeho posloupnosti má podobu: : X_{k+1} = g \cdot X_k~~\bmod~~n, kde modul n je buď prvočíslo nebo mocnina prvočísla, násobicí konstanta g je prvek s vysokým multiplikativním řádem a semínko X je zvolená počáteční hodnota nesoudělná s n.

Příkladem nepříliš vhodně nastaveného Lehmerova generátoru pseudonáhodných čísel je RANDU.

Příklad v C99

Následující příklad v ISO C představuje jednoduchou implementaci Lehmerova generátoru s pevně danými hodnotami (součin může vést k přetečení, proto je nutné přetypování):

uint32_t lcg_rand(uint32_t a) { return ((uint64_t)a * 279470273UL) % 4294967291UL; }

Reference

Kategorie:Generátory pseudonáhodných čísel Kategorie:Modulární aritmetika