Weyl sequence
From Wikipedia, the free encyclopedia
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, 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.
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
