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

#698 in Algorithms

47 downloads per month

MIT license

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.

No runtime deps