4 releases (2 breaking)
| 0.3.0 | Jan 11, 2022 |
|---|---|
| 0.2.1 | Sep 1, 2018 |
| 0.2.0 | Sep 1, 2018 |
| 0.1.0 | Aug 31, 2018 |
#872 in Algorithms
26KB
228 lines
What is it
A quasirandom generator generates values that are more evenly distributed than those generated by a random number generator.
A random number generator (or an approximation, such as a pseudorandom number generator) will tend to produce clumps and gaps. For example, here are 256 points generated by a PRNG and QRNG on a 32x32 grid:
PRNG
X X X X X
X X X X X X X X X X
X X X X X
X X X X
X X X X X
X X X X X X X X
X X X X
X X X X X X X X X X
X X X X X X
X X X X X X X X
X X X X X X X X X X X
X X X X X X
X X X X X X X
X X X X X X
X X X X
X X X X X X X X
X X X X X X X X
X X X X X X X X X X
X X X X X X X
X X X X X X X X
X X X X X X X X X X
X X X X X X X
X X X X X X X X X
X X X X X X
X X X X X X X X
X X X
X X X X X X X X
X X X X X X X X X X X X X
X X X X X
X X X X X X X X X
X X X X X
X X X X X X X X
QRNG
X X X X X X X
X X X X X X X X
X X X X X X X
X X X X X X X X
X X X X X X X X X
X X X X X X X X
X X X X X X X X
X X X X X X X
X X X X X X X X
X X X X X X X X X
X X X X X X X X
X X X X X X X X
X X X X X X X X
X X X X X X X
X X X X X X X X X
X X X X X X X X
X X X X X X X X
X X X X X X X X
X X X X X X X X
X X X X X X X X
X X X X X X X X
X X X X X X X X
X X X X X X X X
X X X X X X X X
X X X X X X X X
X X X X X X X X
X X X X X X X X X
X X X X X X X X
X X X X X X X
X X X X X X X X
X X X X X X X X
X X X X X X X X X
Why is it useful
The error curves of approximation algorithms (such as numerical integration and monte
carlo simulations) are proportional to 1/sqrt(N) when using a traditional PRNG, but 1/N
when using a QRNG.
For example, here are results from the traditional dart-throwing monte carlo pi approximation algorithm with a PRNG and a QRNG.
PRNG
darts estimate error
10000000 3.14124751412 0.0003451395
20000000 3.14106475705 0.0005278965
30000000 3.14134477138 0.0002478822
40000000 3.14174547854 0.0001528250
50000000 3.14179350284 0.0002008492
60000000 3.14167225236 0.0000795988
70000000 3.14160684488 0.0000141913
80000000 3.14162498927 0.0000323357
90000000 3.14146723491 0.0001254187
100000000 3.14148591141 0.0001067422
QRNG
darts estimate error
10000000 3.14160271416 0.0000100606
20000000 3.14160175708 0.0000091035
30000000 3.14159383805 0.0000011845
40000000 3.14159457854 0.0000019250
50000000 3.14159278283 0.0000001292
60000000 3.14159245236 0.0000002012
70000000 3.14159541631 0.0000027627
80000000 3.14159453927 0.0000018857
90000000 3.14159505713 0.0000024035
100000000 3.14159319142 0.0000005378
One can see the error from the QRNG is three orders of magnitude less than the PRNG after 100,000,000 iterations.
What all can it do
The library exposes code that can generate quasirandomly distributed values in up to 32 dimensions. Any type of
value can be produced so long as it implements FromUniform — a trait that constructs a value from an f64
uniformly distributed in [0, 1).
Example usage
use quasirandom::Qrng;
fn compute_pi() {
let mut qrng = Qrng::<(f64, f64)>::new(0.123);
let mut hits = 0.0;
let mut total = 0.0;
for _ in 0..1_000_000 {
let (x, y) = qrng.gen();
if x.hypot(y) < 1.0 {
hits += 1.0;
}
total += 1.0;
}
println!("pi is approximately {}", 4.0 * hits / total);
}
Acknowledgments
The technique used in this generator is directly taken from this blog post by Martin Roberts.