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.

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.