Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Weyl sequence
open-in-new
<h2 id="in-computing">In computing</h2> <p>In <a href="/facts/Computing/Kghtm9fX">computing</a>, an integer version of this sequence is often used to generate a <a href="/facts/Discrete_uniform_distribution/M52SQP5n">discrete uniform distribution</a> 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 <i>k</i> is chosen, <a href="/facts/Relatively_prime/bnCxCXxs">relatively prime</a> to an integer modulus <i>m</i>. In the common case that <i>m</i> is a power of 2, this amounts to requiring that <i>k</i> is odd. </p><p>The sequence of all multiples of such an integer <i>k</i>, </p> 0, <i>k</i>, 2<i>k</i>, 3<i>k</i>, 4<i>k</i>, … is equidistributed modulo <i>m</i>. <p>That is, the sequence of the remainders of each term when divided by <i>m</i> will be uniformly distributed in the interval [0, <i>m</i>). </p><p>The term appears to originate with <a href="/facts/George_Marsaglia/Jlu1Defc">George Marsaglia</a>’s paper "<a href="/facts/Xorshift/N6cr5Tfw">Xorshift</a> RNGs".<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> The following C code generates what Marsaglia calls a "Weyl sequence": </p> d += 362437; <p>In this case, the odd integer is 362437, and the results are computed modulo <i>m</i> = 2<i>32</i> because d is a 32-bit quantity. The results are equidistributed modulo 232. </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/List_of_things_named_after_Hermann_Weyl/7Tw2gvcS">List of things named after Hermann Weyl</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Weyl, H. (September 1916). "Über die Gleichverteilung von Zahlen mod. Eins" [On the uniform distribution of numbers modulo one]. Mathematische Annalen (in German). 77 (3): 313–352. doi:10.1007/BF01475864. S2CID 123470919. <a href="/wiki/Hermann_Weyl" target="_blank">/wiki/Hermann_Weyl</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Kuipers, L.; Niederreiter, H. (2006) [1974]. Uniform Distribution of Sequences. Dover Publications. ISBN 0-486-45019-8. <a href="0-486-45019-8" target="_blank">0-486-45019-8</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Marsaglia, George (July 2003). "Xorshift RNGs". Journal of Statistical Software. 8 (14). doi:10.18637/jss.v008.i14. <a href="/wiki/George_Marsaglia" target="_blank">/wiki/George_Marsaglia</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> </ol>