Normally Distributed Random Number Generator Benchmark

Copyright(c) 2015 Milo Yip ([email protected])

Introduction

This benchmark evaluates the performance of generting random numbers with standard normal distribution. The function prototypes are:

void normaldistf(float* data, size_t n);
void normaldist(double* data, size_t n);

These functions generate n standard normal distributed random numbers (samples), in float and double respectively.

Generating muliple random numbers, instead of generating a single random number, can be suitable for some algorithms (such as Box-Muller generates two numbers at once, and also SIMD versions).

Some implemenetations require data to be 16 or 32 byte aligned, and n to be multiples of 2, 8, 16, 32 etc.

Procedure

Firstly the program verifies the correctness of implementations. The correctness is simply using the following critera:

bool correctness = 
    std::abs(mean    ) < 0.01 &&
    std::abs(sd - 1.0) < 0.01 &&
    std::abs(skewness) < 0.01 &&
    std::abs(kurtosis) < 0.01;

where skewness is Pearson's moment coefficient of skewness and kurtosis is excess kurtosis.

In the benchmark, each trial generates n = 1000000 (1 million) samples. The minimum time duration is measured for 10 trials.

Build and Run

1. Obtain premake4.
2. Copy premake4 executable to normaldist-benchmark/build folder (or system path).
3. Run premake.bat or premake.sh in normaldist-benchmark/build
4. On Windows, build the solution at normaldist-benchmark/build/vs2008/ or /vs2010/.
5. On other platforms, run GNU make config=release32 (or release64) at normaldist-benchmark/build/gmake/
6. On success, run the normaldistXXX executable is generated at normaldist-benchmark/
7. The results in CSV format will be written to normaldist-benchmark/result.
8. Run GNU make in normaldist-benchmark/result to generate results in HTML.

Note that, for platforms not supporting SSE2/AVX, please modify build/premake4.lua and src/test.h.

Implementations

Note that the null implementation generates unform random numbers. It measures the overheads of looping, memory writing, and uniform random number generation. Uniform number generation is included because normally distributed random number generators are based on at least one uniform random number generation.

CLT implementations were actually unable to pass the correctness tests, as their kurtosis are higher than threshold.

All implementations except cpp11random uses simplest linear congruential generator as uniform distributed pseudo random number generator (PRNG).

Some implementations of sse2 and avx version are using math libraries sse_mathfun and avx_mathfun, which provides logarithm and sine/cosine functions.

Results

The following are results measured on a iMac (Core i5 3330S @2.70GHz).

normaldistf (single precision):

normaldist (double precision):

• [email protected]_mac64_clang6.1

FAQ

1. How to add an implementation?

   You may clone an existing implementation file (e.g. boxmuller.cpp). And then modify it. Re-run premake to add it to project or makefile. Note that it will automatically register to the benchmark by macro REGISTER_TEST(name).

   Making pull request of new implementations is welcome.

References

[1] G. E. P. Box and Mervin E. Muller, A Note on the Generation of Random Normal Deviates, The Annals of Mathematical Statistics (1958), Vol. 29, No. 2 pp. 610–611.

[2] Marsaglia, George, and Thomas A. Bray. "A convenient method for generating normal variables." SIAM review 6.3 (1964): 260-264.

[3] Marsaglia, George, and Wai Wan Tsang. "The ziggurat method for generating random variables." Journal of statistical software 5.8 (2000): 1-7.

Related Benchmarks and Discussions

• Generate random numbers following a normal distribution in C/C++