Wichmann–Hill

Wichmann–Hill is a pseudorandom number generator proposed in 1982 by Brian Wichmann and David Hill.[1] It consists of three linear congruential generators with different prime moduli, each of which is used to produce a uniformly distributed number between 0 and 1. These are summed, modulo 1, to produce the result.[2]

Summing three generators produces a pseudorandom sequence with cycle exceeding 6.95×1012.[3] Specifically, the moduli are 30269, 30307 and 30323, producing periods of 30268, 30306 and 30322. The overall period is the least common multiple of these: 30268×30306×30322/4 = 6953607871644. This has been confirmed by a brute-force search.[4][5]

Implementation

The following pseudocode is for implementation on machines capable of integer arithmetic up to 5,212,632:

[r, s1, s2, s3] = function(s1, s2, s3) is
    // s1, s2, s3 should be random from 1 to 30,000. Use clock if available.
    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)

For machines limited to 16-bit signed integers, the following equivalent code only uses numbers up to 30,323:

[r, s1, s2, s3] = function(s1, s2, s3) is
    // s1, s2, s3 should be random from 1 to 30,000. Use clock if available.
    s1 := 171 × mod(s1, 177) − 2 × floor(s1 / 177)
    s2 := 172 × mod(s2, 176) − 35 × floor(s2 / 176)
    s3 := 170 × mod(s3, 178) − 63 × floor(s3 / 178)

    r := mod(s1/30269 + s2/30307 + s3/30323, 1)

The seed values s1, s2 and s3 must be initialized to non-zero values.

References
  1. Wichmann, Brian A.; Hill, I. David (1982). "Algorithm AS 183: An Efficient and Portable Pseudo-Random Number Generator". Journal of the Royal Statistical Society. Series C (Applied Statistics). 31 (2): 188–190. doi:10.2307/2347988. JSTOR 2347988.
  2. McLeod, A. Ian (1985). "Remark AS R58: A Remark on Algorithm AS 183. An Efficient and Portable Pseudo-Random Number Generator". Journal of the Royal Statistical Society. Series C (Applied Statistics). 34 (2): 198–200. doi:10.2307/2347378. JSTOR 2347378. Wichmann and Hill (1982) claim that their generator RANDOM will produce uniform pseudorandom numbers which are strictly greater than zero and less than one. However, depending on the precision of the machine, some zero values may be produced due to rounding error. The problem occurs with single-precision floating point when rounding to zero.
  3. Wichmann, Brian; Hill, David (1984). "Correction: Algorithm AS 183: An Efficient and Portable Pseudo-Random Number Generator". Journal of the Royal Statistical Society. Series C (Applied Statistics). 33 (1): 123. doi:10.2307/2347676. JSTOR 2347676.
  4. Rikitake, Kenji (16 March 2017). "AS183 PRNG algorithm internal state calculator in C". GitHub.
  5. Zeisel, H. (1986). "Remark ASR 61: A Remark on Algorithm AS 183. An Efficient and Portable Pseudo-Random Number Generator". Journal of the Royal Statistical Society. Series C (Applied Statistics). 35 (1): 98. doi:10.1111/j.1467-9876.1986.tb01945.x. JSTOR 2347876. Wichmann and Hill (1982) suggested a pseudo-random generator based on summation of pseudo-random numbers based on summation of pseudo-random numbers generated by multiplicative congruential methods. This, however, is not more than an efficient method to implement a multiplicative congruential generator with a cycle length much greater than the maximal integer. Using the Chinese Remainder Theorem (see e.g. Knuth, 1981) you can prove that you will obtain the same results using only one multiplicative congruential generator Xn+1 = α⋅Xn modulo m with α = 1655 54252 64690, m = 2781 71856 04309. The original version, however, is still necessary to make a generator with such lengthy constants work on ordinary computer arithmetic.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.