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:
gdzie: wartość – liczba pierwsza lub potęga liczby pierwszej, mnożnik – element mający wysoki rząd modulo (na przykład pierwiastek pierwotny), ziarno – liczba względnie pierwsza z
Parametry w powszechnym użyciu W 1988 roku Park i Miller zasugerowali generator Lehmera z parametrami (a liczba Mersenne’a ) i (pierwiastek pierwotny modulo ) 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 (a liczba Fermata ) i (pierwiastek pierwotny modulo )(Zauważmy, że podręcznik ZX81 niepoprawnie twierdzi, że 65537 jest liczbą pierwszą Mersenne’a równą Podręcznik ZX Spectrum poprawił to i poprawnie twierdzi, że jest liczbą pierwszą Fermata równą ).. Generator użyty w komputerze CRAY o nazwie RANF jest generatorem Lehmera z i GNU Scientific Library: Other random number generators.. 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 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 musi być względnie pierwsze do co nie jest wymagane dla LCG w ogólności. Wybór liczby modulo i mnożnika jest także bardziej restrykcyjny dla generatora Lehmera. W przeciwieństwie do LCG, maksymalny okres generatora Lehmera jest równy i jest taki kiedy jest liczbą pierwszą i jest pierwiastkiem pierwotnym modulo
Inaczej mówiąc, Logarytmy dyskretne (o podstawie lub jakimś innym pierwiastku pierwotnym modulo ) z w reprezentują liniową kongruencyjną sekwencję modulo tocjent Eulera
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 232-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 /* Stan musi być zainicjowany przez dwie 64-bitowe wartości, z których s MUSI być nieparzysta. */ static union { __int128 x; uint64_t s; } state;
uint64_t next(void) { state.x *= ((__int128)0x12e15e35b500f16e << 64 | 0x2e714eb2b37916a5); return state.s; }
Generator wylicza nieparzystą 128-bitową wartość i zwraca jej wyższe 64 bitów. Zauważmy, że Note that the role s i s muszą być zamienione w architekturze big-endian.
Ten generator przechodzi przekonujące statystyczne testy takie jak BigCrush z TestU01 i PractRand.
(journal version: Annals of the Computation Laboratory of Harvard University, Vol. 26 (1951)).
Steve Park, Random Number Generators Park-Miller-Carta Pseudo-Random Number Generator
Przypisy
Kategoria:Generowanie liczb losowych