Generator Lehmera

Generator Lehmera^[1] (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}\mod n,

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 edytuj

W 1988 roku Park i Miller^[2] zasugerowali generator Lehmera z parametrami $n=2^{31}-1=2\ 147\ 483\ 647$ (a liczba Mersenne’a $M_{31}$ ) i $g=7^{5}=16\ 807$ (pierwiastek pierwotny modulo $M_{31}$ ) obecnie znany jako MINSTD. Chociaż MINSTD był później krytykowany przez Marsaglię and Sullivana (1993)^[3], 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)^[4]:

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=65\ 537$ (a liczba Fermata $F_{4}$ ) i $g=75$ (pierwiastek pierwotny modulo $F_{4}$ )^[5]. Generator użyty w komputerze CRAY o nazwie RANF jest generatorem Lehmera z $n=2^{48}-1$ i $g=44\ 485\ 709\ 377\ 909$ ^[6]. The GNU Scientific Library zawiera kilka generatorów liczb losowych postaci Lehmera, włączając MINSTD, RANF oraz niesławny generator IBM-u RANDU^[6].

Stosunek do LCG edytuj

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 $\varphi (n).$

Przykład kodu w C99 edytuj

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^[7]. 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.

Lehmer, D.H. Mathematical methods in large-scale computing units. „Proceedings of a Second Symposium on Large-Scale Digital Calculating Machinery”, s. 141–146, 1949. Mathematical Reviews 0044899. (journal version: Annals of the Computation Laboratory of Harvard University, Vol. 26 (1951)).
Martin Greenberger. Notes on a New Pseudo-Random Number Generator. „Journal of the ACM”. 8 (2), s. 163–167, 1961. DOI: 10.1145/321062.321065.
Steve Park, Random Number Generators
Park-Miller-Carta Pseudo-Random Number Generator

Przypisy edytuj

↑ W.H. Payne, J.R. Rabung, T.P. Bogyo. Coding the Lehmer pseudo-random number generator. „Communications of the ACM”. 12 (2), s. 85–86, 1969. DOI: 10.1145/362848.362860.
↑ Stephen K. Park, Keith W. Miller. Random Number Generators: Good Ones Are Hard To Find. „Communications of the ACM”. 31 (10), s. 1192–1201, 1988. DOI: 10.1145/63039.63042.
↑ Marsaglia, George, Sullivan, Stephen. Technical correspondence. „Communications of the ACM”. 36 (7), s. 105–110, 1993. DOI: 10.1145/159544.376068.
↑ Stephen K. Park, Keith W. Miller, Paul K. Stockmeyer. Technical Correspondence. „Communications of the ACM”. 36 (7), s. 105–110, 1988. DOI: 10.1145/159544.376068.
↑ Chapter 5 - Functions. W: Steve Vickers: ZX81 Basic Programming. Sinclair Research Ltd.. Cytat: The ZX81 uses p=65537 & a=75 [...]. (Zauważmy, że podręcznik ZX81 niepoprawnie twierdzi, że 65537 jest liczbą pierwszą Mersenne’a równą $2^{16}-1.$ Podręcznik ZX Spectrum poprawił to i poprawnie twierdzi, że jest liczbą pierwszą Fermata równą $2^{16}+1$ ).
↑ ^a ^b GNU Scientific Library: Other random number generators.
↑ Pierre L’Ecuyer. Tables of linear congruential generators of different sizes and good lattice structure. „Mathematics of Computation”. 68 (225), s. 249–260, January 1999. DOI: 10.1090/s0025-5718-99-00996-5.

[1] W.H. Payne, J.R. Rabung, T.P. Bogyo. Coding the Lehmer pseudo-random number generator. „Communications of the ACM”. 12 (2), s. 85–86, 1969. DOI: 10.1145/362848.362860.

[2] Stephen K. Park, Keith W. Miller. Random Number Generators: Good Ones Are Hard To Find. „Communications of the ACM”. 31 (10), s. 1192–1201, 1988. DOI: 10.1145/63039.63042.

[3] Marsaglia, George, Sullivan, Stephen. Technical correspondence. „Communications of the ACM”. 36 (7), s. 105–110, 1993. DOI: 10.1145/159544.376068.

[4] Stephen K. Park, Keith W. Miller, Paul K. Stockmeyer. Technical Correspondence. „Communications of the ACM”. 36 (7), s. 105–110, 1988. DOI: 10.1145/159544.376068.

[5] Chapter 5 - Functions. W: Steve Vickers: ZX81 Basic Programming. Sinclair Research Ltd.. Cytat: The ZX81 uses p=65537 & a=75 [...]. (Zauważmy, że podręcznik ZX81 niepoprawnie twierdzi, że 65537 jest liczbą pierwszą Mersenne’a równą $2^{16}-1.$ Podręcznik ZX Spectrum poprawił to i poprawnie twierdzi, że jest liczbą pierwszą Fermata równą $2^{16}+1$ ).

[gnu-6] GNU Scientific Library: Other random number generators.

[7] Pierre L’Ecuyer. Tables of linear congruential generators of different sizes and good lattice structure. „Mathematics of Computation”. 68 (225), s. 249–260, January 1999. DOI: 10.1090/s0025-5718-99-00996-5.

[1]

[2]

[3]

[4]

[5]

[6]

[7]