ziggurat

ziggurat

The Ziggurat Algorithm is an extremely fast algorithm for the random sampling from arbitrary probability distributions. Just pass your distribution as input, and get a random number generator as output.

What

The goal of random number generation is to sample from the area under the probability distribution curve. The Ziggurat algorithm does this by covering the probability distribution up into equal areas with a large number of rectangles, which just barely exceed the area of the probability distribution, then samples from a random point in a randomly selected rectangle. There is a very small chance that the sampled point lies outside the probability distribution, in which case we simply retry (with the same rectangle). With enough rectangles, you can construct them such that the probability of landing outside the probability distribution is extremely small, and in the vast majority of cases, sampling a random point from the distribution is equivalent to picking a random point in rectangle.

This code enables the automated construction of these extremely fast random number generators for unimodal, univariate probability distributions. This code is closely integrated with gonum, so you can supply most gonum distributions as input and get your fast(er) random number generator as output. You can also write your own distributions as long as they fulfill the ziggurat.Distribution interface.

For fastest results, I recommend using xorshift as your random source.

Why

Fast random number generation is very important for large-scale Monte Carlo simulations, commonly used in scientific computing and statistics. Random number generation is often the bottleneck in these simulations, and I needed this code to run my own simulations at as large a scale as possible.

For the normal distribution and exponentiatial distribution, the Go standard library already uses pre-built hand-optimized Ziggurat algorithms to generate fast random numbers, so this library will not outperform them; however this library enables the creation of similarly-performing algorithms for arbitrary probability distributions (e.g. Triangle, Gamma, and Students' T distributions), and is much faster than existing libraries in those cases.

How

package main

import (
	"github.com/argusdusty/ziggurat"
	"github.com/vpxyz/xorshift/xorshift64star"
	"gonum.org/v1/gonum/stat/distuv"
)

func main() {
	src := xorshift64star.NewSource(1)
	distribution := distuv.UnitNormal // Swap this for most gonum univariate distributions
	rng := ziggurat.ToSymmetricZiggurat(distribution, src) // The normal distribution is symmetric, so we can use the more efficient symmetric ziggurat
	randomNormalValue := rng.Rand()
}

Note that gonum 1.16.0 is required due to the use of math/rand/v2.

Benchmarks

ziggurat>go test -bench=. -cpu=1 -benchtime=5s
goos: windows
goarch: amd64
pkg: github.com/argusdusty/ziggurat
cpu: AMD Ryzen 9 5900X 12-Core Processor

(Note: Fast RNG means xorshift64star)