Editing Low-discrepancy sequence (section)

===Additive recurrence===

For any irrational <math>\alpha</math>, the sequence

: <math>s_n = \{s_0 + n\alpha\}</math>

has discrepancy tending to <math>1/N</math>. Note that the sequence can be defined recursively by
: <math>s_{n+1} = (s_n + \alpha)\bmod 1 \;.</math>

A good value of <math>\alpha</math> gives lower discrepancy than a sequence of independent uniform random numbers.

The discrepancy can be bounded by the [[approximation exponent]] of <math>\alpha</math>. If the approximation exponent is <math>\mu</math>, then for any <math>\varepsilon>0</math>, the following bound holds:<ref name="kn05">{{Harvnb|Kuipers|Niederreiter|2005|p=123}}</ref>

: <math> D_N((s_n)) = O_\varepsilon (N^{-1/(\mu-1)+\varepsilon}).</math>

By the [[Thue–Siegel–Roth theorem]], the approximation exponent of any irrational algebraic number is 2, giving a bound of <math>N^{-1+\varepsilon}</math> above.

The recurrence relation above is similar to the recurrence relation used by a [[linear congruential generator]], a poor-quality pseudorandom number generator:<ref>{{Cite book|first=Donald E. |last= Knuth |title=[[The Art of Computer Programming]] |volume=2 |chapter=Chapter 3 – Random Numbers}}</ref>

: <math>r_i = (a r_{i-1} + c) \bmod m</math>

For the low discrepancy additive recurrence above, ''a'' and ''m'' are chosen to be 1.  Note, however, that this will not generate independent random numbers, so should not be used for purposes requiring independence.  

The value of <math>c</math> with lowest discrepancy is the fractional part of the [[golden ratio]]:<ref>
{{Cite web|first=Malte |last=Skarupke|url=https://probablydance.com/2018/06/16/fibonacci-hashing-the-optimization-that-the-world-forgot-or-a-better-alternative-to-integer-modulo/ |title=Fibonacci Hashing: The Optimization that the World Forgot|date=16 June 2018 |quote=One property of the Golden Ratio is that you can use it to subdivide any range roughly evenly ... if you don’t know ahead of time how many steps you’re going to take}}
</ref>

: <math>c = \frac{\sqrt{5}-1}{2} = \varphi - 1 \approx 0.618034.</math>

Another value that is nearly as good is the fractional part of the [[silver ratio]], which is the fractional part of the square root of 2:

: <math>c = \sqrt{2}-1 \approx 0.414214. \, </math>

In more than one dimension, separate quasirandom numbers are needed for each dimension. A convenient set of values that are used, is the square roots of [[primes]] from two up, all taken modulo 1:

: <math>c = \sqrt{2}, \sqrt{3}, \sqrt{5}, \sqrt{7}, \sqrt{11}, \ldots \, </math>

However, a set of values based on the generalised golden ratio has been shown to produce more evenly distributed points. <ref>{{Cite web|first=Martin |last=Roberts|year= 2018 |url=https://web.archive.org/web/20250301162105/https://extremelearning.com.au/unreasonable-effectiveness-of-quasirandom-sequences/ |title=The Unreasonable Effectiveness of Quasirandom Sequences}}
</ref>

The [[list of pseudorandom number generators]] lists methods for generating independent pseudorandom numbers.
''Note'': In few dimensions, recursive recurrence leads to uniform sets of good quality, but for larger <math>s</math> (like <math> s>8 </math>) other point set generators can offer much lower discrepancies.