Weyl sequence
In mathematics, a Weyl sequence is a sequence from the equidistribution theorem proven by Hermann Weyl:{{cite journal|last=Weyl|first=H.| author-link=Hermann Weyl |title=Über die Gleichverteilung von Zahlen mod. Eins |trans-title=On the uniform distribution of numbers modulo one |language=de |journal=Mathematische Annalen |date=September 1916 |volume=77|pages=313–352 | doi = 10.1007/BF01475864 | issue = 3|s2cid=123470919|url=https://zenodo.org/record/2425535}}
The sequence of all multiples of an irrational α,
::0, α, 2α, 3α, 4α, ...
:is equidistributed modulo 1.{{cite book | first1=L. | last1=Kuipers | first2=H. | last2=Niederreiter |author2-link = Harald Niederreiter | title=Uniform Distribution of Sequences | publisher=Dover Publications | year=2006 | orig-year=1974 | isbn=0-486-45019-8 }}
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 {{nowrap begin}}[0, m{{nowrap end}}).
The term appears to originate with George Marsaglia’s paper "Xorshift RNGs".{{cite journal
| first=George | last=Marsaglia | author-link=George Marsaglia
| title=Xorshift RNGs
| journal=Journal of Statistical Software
| volume=8 | issue=14
| date=July 2003
| url=http://www.jstatsoft.org/v08/i14/paper | doi=10.18637/jss.v008.i14| doi-access=free}}
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 {{nowrap|1=m = 232}} because d is a 32-bit quantity. The results are equidistributed modulo 232.