Wichmann–Hill

Wichmann–Hill är en pseudoslumptalsgenerator som föreslogs 1982 av Brian Wichmann och David Hill. Den består av tre linjära kongruentialgeneratorer med olika primmoduler , som var och en används för att producera ett enhetligt fördelat tal mellan 0 och 1. Dessa summeras, modulo 1, för att producera resultatet.

Att summera tre generatorer ger en pseudoslumpsekvens med en cykel som överstiger 6,95 × 10 ¹² . Specifikt är modulerna 30269, 30307 och 30323, vilket ger perioder på 30268, 30306 och 30322. Den totala perioden är den 6 748 6 minsta gemensamma multipeln av dessa: 30268×30306×30322/4 = . Detta har bekräftats av en brute-force-sökning .

Genomförande

Följande pseudokod är avsedd för implementering på maskiner som kan heltalsaritmetik upp till 5 212 632 :

    
     [r, s1, s2, s3] =  funktion  (  s1  ,  s2  ,  s3  )  är  // s1, s2, s3 ska vara slumpmässigt från 1 till 30 000. Använd klocka om tillgänglig.   s1  := mod(171 ×  s1  , 30269)  s2  := mod(172 ×  s2  , 30307)  s3  := mod(170 ×  s3  , 30323)  r  := mod(  s1  /30269.0 + s2 /300 +   s2  /303,303 + s2 /300 +  s2  /300 + 1)

För maskiner som är begränsade till 16-bitars signerade heltal, använder följande ekvivalenta kod endast nummer upp till 30 323 :

    
     [r, s1, s2, s3] =  funktion  (  s1  ,  s2  ,  s3  )  är  // s1, s2, s3 ska vara slumpmässigt från 1 till 30 000. Använd klocka om tillgänglig.   s1  := 171 × mod(  s1  , 177) − 2 × golv(  s1  / 177)  s2  := 172 × mod(  s2  , 176) − 35 × golv(  s2  / 176)  s3  := 170 × mod(  s8  , 73 )  ) − 63 × golv(   s3  / 178)  r  := mod(s1/30269 + s2/30307 + s3/30323, 1)

Frövärdena s1 , s2 och s3 måste initieras till värden som inte är noll.

^ Wichmann, Brian A.; Hill, I. David (1982). "Algorithm AS 183: En effektiv och bärbar pseudo-slumptalsgenerator". Journal of the Royal Statistical Society. Serie C (tillämpad statistik) . 31 (2): 188–190. doi : 10.2307/2347988 . JSTOR 2347988 .
^ McLeod, A. Ian (1985). "Anmärkning AS R58: A Remark on Algorithm AS 183. En effektiv och bärbar pseudo-slumptalsgenerator". Journal of the Royal Statistical Society. Serie C (tillämpad statistik) . 34 (2): 198–200. doi : 10.2307/2347378 . JSTOR 2347378 . Wichmann och Hill (1982) hävdar att deras generator RANDOM kommer att producera enhetliga pseudoslumptal som är strikt större än noll och mindre än ett. Beroende på maskinens precision kan dock vissa nollvärden skapas på grund av avrundningsfel. Problemet uppstår med flyttal med enkel precision vid avrundning till noll.
^ Wichmann, Brian; Hill, David (1984). "Korrigering: Algoritm AS 183: En effektiv och bärbar pseudo-slumptalsgenerator". Journal of the Royal Statistical Society. Serie C (tillämpad statistik) . 33 (1): 123. doi : 10.2307/2347676 . JSTOR 2347676 .
^ Rikitake, Kenji (16 mars 2017). "AS183 PRNG-algoritm intern tillståndskalkylator i C" . GitHub .
^ Zeisel, H. (1986). "Anmärkning ASR 61: A Remark on Algorithm AS 183. En effektiv och bärbar pseudo-slumptalsgenerator" . Journal of the Royal Statistical Society. Serie C (tillämpad statistik) . 35 (1): 98. doi : 10.1111/j.1467-9876.1986.tb01945.x . JSTOR 2347876 . Wichmann och Hill (1982) föreslog en pseudoslumpgenerator baserad på summering av pseudoslumptal baserat på summering av pseudoslumptal genererade med multiplikativa kongruentiella metoder. Detta är emellertid inte mer än en effektiv metod för att implementera en multiplikativ kongruentialgenerator med en cykellängd som är mycket större än det maximala heltal. Med hjälp av den kinesiska restsatsen (se t.ex. Knuth, 1981 ) kan du bevisa att du kommer att få samma resultat med endast en multiplikativ kongruentialgenerator $X n +1 = α \cdot X n modulo m$ med $α = 1655 54252 64690$ , $m = 28781 . 04309$ . Den ursprungliga versionen är dock fortfarande nödvändig för att få en generator med så långa konstanter att fungera på vanlig datoraritmetik.

[1] Wichmann, Brian A.; Hill, I. David (1982). "Algorithm AS 183: En effektiv och bärbar pseudo-slumptalsgenerator". Journal of the Royal Statistical Society. Serie C (tillämpad statistik) . 31 (2): 188–190. doi : 10.2307/2347988 . JSTOR 2347988 .

[2] McLeod, A. Ian (1985). "Anmärkning AS R58: A Remark on Algorithm AS 183. En effektiv och bärbar pseudo-slumptalsgenerator". Journal of the Royal Statistical Society. Serie C (tillämpad statistik) . 34 (2): 198–200. doi : 10.2307/2347378 . JSTOR 2347378 . Wichmann och Hill (1982) hävdar att deras generator RANDOM kommer att producera enhetliga pseudoslumptal som är strikt större än noll och mindre än ett. Beroende på maskinens precision kan dock vissa nollvärden skapas på grund av avrundningsfel. Problemet uppstår med flyttal med enkel precision vid avrundning till noll.

[3] Wichmann, Brian; Hill, David (1984). "Korrigering: Algoritm AS 183: En effektiv och bärbar pseudo-slumptalsgenerator". Journal of the Royal Statistical Society. Serie C (tillämpad statistik) . 33 (1): 123. doi : 10.2307/2347676 . JSTOR 2347676 .

[4] Rikitake, Kenji (16 mars 2017). "AS183 PRNG-algoritm intern tillståndskalkylator i C" . GitHub .

[5] Zeisel, H. (1986). "Anmärkning ASR 61: A Remark on Algorithm AS 183. En effektiv och bärbar pseudo-slumptalsgenerator" . Journal of the Royal Statistical Society. Serie C (tillämpad statistik) . 35 (1): 98. doi : 10.1111/j.1467-9876.1986.tb01945.x . JSTOR 2347876 . Wichmann och Hill (1982) föreslog en pseudoslumpgenerator baserad på summering av pseudoslumptal baserat på summering av pseudoslumptal genererade med multiplikativa kongruentiella metoder. Detta är emellertid inte mer än en effektiv metod för att implementera en multiplikativ kongruentialgenerator med en cykellängd som är mycket större än det maximala heltal. Med hjälp av den kinesiska restsatsen (se t.ex. Knuth, 1981 ) kan du bevisa att du kommer att få samma resultat med endast en multiplikativ kongruentialgenerator $X n +1 = α \cdot X n modulo m$ med $α = 1655 54252 64690$ , $m = 28781 . 04309$ . Den ursprungliga versionen är dock fortfarande nödvändig för att få en generator med så långa konstanter att fungera på vanlig datoraritmetik.