Generator Lehmera

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

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:

gdzie wartość n jest liczbą pierwszą lub potęgą liczby pierwszej, mnożnik g jest elementem mającym wysoki rząd modulo n (na przykład pierwiastek pierwotny) a ziarno X0 jest liczbą względnie pierwszą z n.

Parametry w powszechnym użyciu[edytuj | edytuj kod]

W 1988 roku Park i Miller[2] zasugerowali generator Lehmera z parametrami n = 231 − 1 = 2'147'483'647 (a liczba Mersenne’a M31) i g = 75 = 16'807 (pierwiastek pierwotny modulo M31) 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 = 216 + 1 = 65'537 (a liczba Fermata F4) and g = 75 (pierwiastek pierwotny modulo F4). [5] Generator użyty w komputerze CRAY o nazwie RANF jest generatorem Lehmera z n = 248 − 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 | edytuj kod]

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 X0 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 Xk w reprezentują liniową kongruencyjną sekwencję modulo tocjent Eulera .

Przykład kodu w C99[edytuj | edytuj kod]

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[7]. Ma on cykl 2126:

/* 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 | edytuj kod]

  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ą 216-1. Podręcznik ZX Spectrum poprawił to i poprawnie twierdzi, że jest liczbą pierwszą Fermata równą 216+1.)
  6. a b 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.