qmc: evenly spread points for Go

Many programs need random points: to estimate an integral, to sample a parameter space, or to send rays through a room. Random points are easy to make, but they clump and leave gaps. Quasi-Monte Carlo sequences such as Sobol and Halton place points so that they fill the space evenly, and for many problems that gives the same accuracy with far fewer points. qmc is a small Go library for these sequences, with no dependencies. I started it in August and have just given it a thorough review.

Three squares with 256 points each: random points with clumps and gaps, Halton and Sobol points spread evenly
256 points each, over a 16 × 16 grid. The random points leave 100 of the 256 cells empty, Halton leaves 44, and Sobol puts exactly one point in every cell.

Using it

A generator is created for a number of dimensions and then hands out points with coordinates between 0 and 1:

g, err := qmc.NewSobol(2, qmc.WithOwenScrambling(seed))
if err != nil {
    return err
}
for i := 0; i < 1024; i++ {
    p := g.Next() // p[0], p[1] in [0,1)
    // use p
}

Sobol works up to 1,024 dimensions with the built-in Joe–Kuo direction numbers. Halton has no fixed limit. Both can be scrambled with a seed, which keeps the even spread but gives a different point set for each seed, so you can run several and see how much the result varies. At(i) returns the i-th point directly, and several goroutines can call it at once.

Does it help?

The classic toy example: throw points into the unit square and count how many land inside the quarter circle. Four times that fraction approximates π. The plot shows the mean error over 20 runs, with random points and with scrambled Sobol points:

Log-log plot of the error when estimating pi: the Sobol line falls much faster than the random line
With 1,024 Sobol points the error is about as small as with 16,000 to 65,000 random points. The gap grows with the number of points.

The gain depends on the problem. It is largest for smooth functions in few dimensions, and it shrinks in many dimensions or with sharp edges. So it is worth measuring on your own problem before switching.

Trying it

The web demo runs the library as WebAssembly in your browser. Its Point Lab starts with a guided tour through scatter plots, scrambling, correlation and convergence, and a second page compares the sequences by discrepancy, a number for how evenly points are spread. The library itself is one go get github.com/cwbudde/qmc away.