Weyl sequence
 | This article, Weyl sequence, has recently been created via the Articles for creation process. Please check to see if the reviewer has accidentally left this template after accepting the draft and take appropriate action as necessary.
Reviewer tools: Inform author |
Comment: Awaiting feedback from experts at WikiProject_Mathematics Curb Safe Charmer (talk) 12:33, 2 May 2018 (UTC)
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. An irrational number cannot be represented on a digital computer and an integer is used in its place. An integer version of the theorem with k < 2n is shown below.
The sequence of all multiples of an odd integer k,
- 0, k, 2k, 3k, 4k, …
- is equidistributed modulo 2n.
That is, the sequence of the remainders of each term when divided by 2n will be uniformly distributed in the interval [0, 2n).
An example of such a sequence is shown in 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. The results are equidistributed modulo 2 because d is a 32-bit quantity.
It is likely that Marsaglia’s paper is the origin of the integer “Weyl sequence” used in computing.
See also
References
- ^ Weyl, H. (1916). "Ueber die Gleichverteilung von Zahlen mod. Eins,". Math. Ann. 77 (3): 313–352. doi:10.1007/BF01475864.
- ^ Kuipers, L.; Niederreiter, H. (2006) [1974]. Uniform Distribution of Sequences. Dover Publications. ISBN 0-486-45019-8.
- ^ Marsaglia, George (July 2003). "Xorshift RNGs". Journal of Statistical Software. 8 (14). doi:10.18637/jss.v008.i14.
{{cite journal}}: Cite has empty unknown parameter:|1=(help)