Wichmann – Hill - Wichmann–Hill

Wichmann – Hill je generátor pseudonáhodných čísel v roce 1982 navrhl Brian Wichmann a David Hill.[1] Skládá se ze tří lineární shodné generátory s různými primární moduly, z nichž každý se používá k výrobě a rovnoměrně rozloženo číslo mezi 0 a 1. Ty se sečtou, modulo 1, aby se dosáhlo výsledku.[2]

Součet tří generátorů vytvoří pseudonáhodnou sekvenci s překročením cyklu 6.95×1012.[3] Konkrétně jsou to moduly 30269, 30307 a 30323, produkující periody 30268, 30306 a 30322. Celkovým obdobím je nejmenší společný násobek z toho: 30268 × 30306 × 30322/4 = 6953607871644. To bylo potvrzeno a vyhledávání hrubou silou.[4][5]

Implementace

Následující pseudo kód je pro implementaci na strojích schopných celočíselné aritmetiky až do 5212632:

[r, s1, s2, s3] = funkce(s1, s2, s3) je    // s1, s2, s3 by měly být náhodné od 1 do 30 000. Pokud jsou k dispozici, použijte hodiny.    s1 : = mod (171 × s1, 30269)    s2 : = mod (172 × s2, 30307)    s3 : = mod (170 × s3, 30323)    r : = mod (s1/30269.0 + s2/30307.0 + s3/30323.0, 1)

U strojů omezených na 16bitová celá čísla se znaménkem používá následující ekvivalentní kód pouze čísla do 30 323:

[r, s1, s2, s3] = funkce(s1, s2, s3) je    // s1, s2, s3 by měly být náhodné od 1 do 30 000. Pokud jsou k dispozici, použijte hodiny.    s1 : = 171 × mod (s1, 177) - 2 × patro (s1 / 177)    s2 : = 172 × mod (s2, 176) - 35 × podlaha (s2 / 176)    s3 : = 170 × mod (s3, 178) - 63 × podlaha (s3 / 178)    r : = mod (s1 / 30269 + s2 / 30307 + s3 / 30323, 1)

Počáteční hodnoty s1, s2 a s3 musí být inicializován na nenulové hodnoty.

Reference

  1. ^ Wichmann, Brian A .; Hill, I. David (1982). "Algoritmus AS 183: Efektivní a přenosný generátor pseudonáhodných čísel". Journal of the Royal Statistical Society. Series C (Applied Statistics). 31 (2): 188–190. doi:10.2307/2347988.
  2. ^ McLeod, A. Ian (1985). „Poznámka AS R58: Poznámka k algoritmu AS 183. Efektivní a přenosný generátor pseudonáhodných čísel“. Journal of the Royal Statistical Society. Series C (Applied Statistics). 34 (2): 198–200. doi:10.2307/2347378. Wichmann a Hill (1982) tvrdí, že jejich generátor RANDOM bude produkovat jednotná pseudonáhodná čísla, která jsou striktně větší než nula a menší než jedna. V závislosti na přesnosti stroje však mohou být kvůli chybě zaokrouhlení vytvořeny některé nulové hodnoty. Problém nastává u plovoucí desetinná čárka s přesnou přesností když zaokrouhlování na nulu.
  3. ^ Wichmann, Brian; Hill, David (1984). "Oprava: Algoritmus AS 183: Efektivní a přenosný generátor pseudonáhodných čísel". Journal of the Royal Statistical Society. Series C (Applied Statistics). 33 (1): 123. doi:10.2307/2347676.
  4. ^ Rikitake, Kenji. "Interní stavová kalkulačka algoritmu AS183 PRNG v C".
  5. ^ Zeisel, H. (1986). „Poznámka ASR 61: Poznámka k algoritmu AS 183. Efektivní a přenosný generátor pseudonáhodných čísel“. Journal of the Royal Statistical Society. Series C (Applied Statistics). 35 (1): 98. doi:10.2307/2347676. Wichmann a Hill (1982) navrhli pseudonáhodný generátor založený na sčítání pseudonáhodných čísel na základě sčítání pseudonáhodných čísel generovaných multiplikativními shodnými metodami. To však není víc než efektivní metoda implementace multiplikativního kongruentního generátoru s délkou cyklu mnohem větší než maximální celé číslo. Za použití Čínská věta o zbytku (viz např. Knuth, 1981 ) můžete prokázat, že získáte stejné výsledky pouze pomocí jednoho multiplikativního generátoru shodných údajů Xn+1 = α⋅Xn modulo m s α = 1655 54252 64690, m = 2781 71856 04309. Původní verze je však stále nutná k tomu, aby generátor s tak zdlouhavými konstantami pracoval na běžné počítačové aritmetice.