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

V tomto článku byl použit překlad textu z článku Lehmer random number generator na anglické Wikipedii.