Weyl sequence

From HandWiki

In mathematics, a Weyl sequence is a sequence from the equidistribution theorem proven by Hermann Weyl:[1] The sequence of all multiples of an irrational α,

0, α, 2α, 3α, 4α, ...
is equidistributed modulo 1.[2]

In other words, the sequence of the fractional parts of each term will be uniformly distributed in the interval [0, 1).

In computing

In computing, an integer version of this sequence is often used to generate a discrete uniform distribution rather than a continuous one. Instead of using an irrational number, which cannot be calculated on a digital computer, the ratio of two integers is used in its place. An integer k is chosen, relatively prime to an integer modulus m. In the common case that m is a power of 2, this amounts to requiring that k is odd.

The sequence of all multiples of such an integer k,

0, k, 2k, 3k, 4k, …
is equidistributed modulo m.

That is, the sequence of the remainders of each term when divided by m will be uniformly distributed in the interval [0, m).

The term appears to originate with George Marsaglia’s paper "Xorshift RNGs".[3] The following C code generates what Marsaglia calls a "Weyl sequence":

d += 362437;

In this case, the odd integer is 362437, and the results are computed modulo m = 232 because d is a 32-bit quantity. The results are equidistributed modulo 232.

See also

  • List of things named after Hermann Weyl

References

  1. Weyl, H. (September 1916). "Über die Gleichverteilung von Zahlen mod. Eins" (in de). Mathematische Annalen 77 (3): 313–352. doi:10.1007/BF01475864. https://zenodo.org/record/2425535. 
  2. Kuipers, L.; Niederreiter, H. (2006). Uniform Distribution of Sequences. Dover Publications. ISBN 0-486-45019-8. 
  3. "Xorshift RNGs". Journal of Statistical Software 8 (14). July 2003. doi:10.18637/jss.v008.i14. http://www.jstatsoft.org/v08/i14/paper.