ZMG: Ziggurat Method Generator of Zero-Mean Gaussians
What is it?
A C-language function for generating pseudorandom variates from the standard normal distribution.
How Does it Work?
It generates the x coordinate of points uniformly drawn from the hypograph (i.e., the region under the curve) of the probability density function (pdf). The hypograph is covered with a union of equal-area rectangles (from which sampling x is very easy), nonuniform trapezoids (from which sampling is moderately easy), and a tail region (from which sampling is more complicated). Points that land outside of the hypograph are rejected. All of the details are provided in a technical report.
Is it Fast?
Yes! Very easy sampling (from a rectangle) occurs with probability 253/256, and all that is required to generate a sample is a uniformly distributed integer, some bit-shifting and masking, an integer comparison, a table lookup, and a single floating-point multiplication. Most of the rest of the time, sampling is performed efficiently in small trapezoidal regions with only a rare need to evaluate the pdf. Even more rarely (just once in every 3611 samples, on average) a point must be sampled from the tail (which, in this implementation, requires evaluation of logarithms and exponential functions).
Where Can I Download it?
Here. Since this package uses a PCG Random Number Generator, you will also need to download the C Implementation (not the minimal C Implementation) of the PCG family of pseudrandom number generators, available here.
After unzipping, simply
follow the instructions in the file README.md.
Is it Easy to Use?
Yes! A complete user's guide can be found in the
file guide.md supplied with ZMG.
Here is a small working example, invoking zmgf,
the float version. (There is also a slower double-precision version,
called zmgd.)
#include <stdio.h>
#include "zmg.h"
#define N 1000000
int main()
{
ZMG_STATE state;
double x, m1, m2;
int i;
seedzmgf(&state); /* seed with system entropy */
m1 = m2 = 0.0;
for (i=0; i<N; ++i)
{
m1 += (x = (double)zmgf(&state));
m2 += (x*x);
}
printf("After %d trials:\n",N);
printf(" 1st sample moment = %f (expect 0)\n",m1/N);
printf(" 2nd sample moment = %f (expect 1)\n",m2/N);
return 0;
}
Save the example shown above in a file called example.c, and
make sure that your working directory contains zmgf.c, zmg.h, and pcg_variants.h (the latter is from the PCG package).
Copy the the following into a Makefile. Then
type make. This should successfully compile the example,
leaving an executable ./example.
CC = gcc
CFLAGS = -Wall -O3 -flto
LIBS = -lm
%.o: %.c
$(CC) -c $(CFLAGS) $<
example: example.o zmgf.o
$(CC) $(CFLAGS) -o $@ $^ $(LIBS)
-flto flag, enabling link-time
optimization. More examples can be found in the test
subdirectory supplied with ZMG.