Generator Lehmera

Generator Lehmera (nazwany ze względu na Derricka Henry’ego Lehmera), czasami nazywany jest generatorem liczb losowych Parka-Millera (ze względu na Stephena K. Parka and Keitha W. Millera), jest rodzajem Liniowego generatora kongruentnego (LCG), który działa na multiplikatywnej grupie modulo n. Ogólnym wzorem jest:

$X_{k+1}=g\cdot X_{k}modn,$

gdzie:

wartość $n$ – liczba pierwsza lub potęga liczby pierwszej,

mnożnik $g$ – element mający wysoki rząd modulo $n$ (na przykład pierwiastek pierwotny),

ziarno $X_0$ – liczba względnie pierwsza z $n.$

Parametry w powszechnym użyciu

W 1988 roku Park i Miller zasugerowali generator Lehmera z parametrami $n=2^{31}-1=2147483647$ (a liczba Mersenne’a $M_{31}$) i $g=7^5=16807$ (pierwiastek pierwotny modulo $M_{31}$) obecnie znany jako MINSTD. Chociaż MINSTD był później krytykowany przez Marsaglię and Sullivana (1993), pozostał w użyciu do dzisiaj (w szczególności w CarbonLib i minstd_rand0 z C++11). Park, Miller i Stockmeyer odpowiedzieli na krytykę (1993):

Ze względu na dynamiczną naturę dziedziny jest trudne dla niespecjalistów powziąć decyzję, jakiego generatora użyć. „Daj mi cokolwiek, co mogę zrozumieć, zaimplementować i zaportować... nie musi być innowacyjne, wystarczy że upewni mnie że jest dość dobre i wydajne”. Nasz artykuł i powiązany z nim generator minimalnego standardu był próbą odpowiedzi na to żądanie. Pięć lat później nie widzimy w naszej odpowiedzi potrzeby zmiany innej niż zasugerować użycie mnożnika a = 48271 zamiast 16807.

Zmieniona stała jest użyta w generatorze liczb pseudolosowych minstd_rand z C++11.

W Sinclair ZX-81 i jego następcach użyto generator Lehmera z parametrami $n=2^{16}+1=65537$ (a liczba Fermata $F_4$) i $g=75$ (pierwiastek pierwotny modulo $F_4$). Generator użyty w komputerze CRAY o nazwie RANF jest generatorem Lehmera z $n=2^{48}-1$ i $g=44485709377909$. The GNU Scientific Library zawiera kilka generatorów liczb losowych postaci Lehmera, włączając MINSTD, RANF oraz niesławny generator IBM-u RANDU.

Stosunek do LCG

Choć generator Lehmera może być postrzegany jako szczególny przypadek liniowego generatora kongruencyjnego (LCG) z $c=0,$ jest to specjalny przypadek, który pociąga za sobą pewne ograniczenia i właściwości. W szczególności dla generatora Lehmera ziarno inicjujące $X_0$ musi być względnie pierwsze do $n,$ co nie jest wymagane dla LCG w ogólności. Wybór liczby modulo $n$ i mnożnika $g$ jest także bardziej restrykcyjny dla generatora Lehmera. W przeciwieństwie do LCG, maksymalny okres generatora Lehmera jest równy $n-1$ i jest taki kiedy $n$ jest liczbą pierwszą i $g$ jest pierwiastkiem pierwotnym modulo $n.$

Inaczej mówiąc, Logarytmy dyskretne (o podstawie $g$ lub jakimś innym pierwiastku pierwotnym modulo $n$) z $X_k$ w ${\mathbb{Z}}_n$ reprezentują liniową kongruencyjną sekwencję modulo tocjent Eulera $\phi (n).$

Przykład kodu w C99

Używając kodu C, generator Lehmera może być zapisany następująco:

#define M 2147483647 /* 2^31 - 1 (Duża liczba pierwsza) */
#define A 16807      /* Pierwiastek pierwotny M, przechodzi testy statystyczne i wytwarza pełny cykl */
#define Q 127773 /* M / A (By uniknąć nadmiaru dla A * seed) */
#define R 2836   /* M % A (By uniknąć nadmiaru dla A * seed) */

uint32_t lcg_parkmiller(uint32_t seed)
{
    uint32_t hi = seed / Q;
    uint32_t lo = seed % Q;
    int32_t test = A * lo - R * hi;
    if (test <= 0)
        test += M;
    return test;
}

Liczba wyjściowa tej funkcji może być z powrotem wkładana jako wejście do generowania liczb pseudolosowych, tak długo jak wołający uważa, by nie zaczynać od zera. Jeśli iloczyn dwóch 32-bitowych liczb spowoduje nadmiar (poniższy przykład), niezbędna jest zmiana typu na uint64_t.

Inna popularna para generatorów Lehmera używa liczb pierwszych modulo 2³²-5:

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

Wiele innych generatorów Lehmera i liczb pierwszych ma dobre własności. Następujący 128-bitowy generator Lehmera wymaga 128-bitowego wspomagania przez kompilator i używa mnożnika obliczonego przez L’Ecuyera. Ma on cykl $2^{126}:$

/* Stan musi być zainicjowany przez dwie 64-bitowe wartości, z których s[0] MUSI być nieparzysta. */
static union {
        __int128 x;
        uint64_t s[2];
} state;

uint64_t next(void) {
        state.x *= ((__int128)0x12e15e35b500f16e << 64 | 0x2e714eb2b37916a5);
        return state.s[1];
}

Generator wylicza nieparzystą 128-bitową wartość i zwraca jej wyższe 64 bitów. Zauważmy, że Note that the role s[0] i s[1] muszą być zamienione w architekturze big-endian.

Ten generator przechodzi przekonujące statystyczne testy takie jak BigCrush z TestU01 i PractRand.

• Szablon:Cytuj pismo (journal version: Annals of the Computation Laboratory of Harvard University, Vol. 26 (1951)).
• Szablon:Cytuj pismo
• Steve Park, Random Number Generators
• Park-Miller-Carta Pseudo-Random Number Generator