A new pseudo-random number generator for Haskell

I just released version 0.3.3 of the Haskell statistics library, which contains a very fast pseudo-random number generator.

The generator is an implementation of George Marsaglia’s MWC256 multiply-with-carry PRNG, which has a period of 28222 (for this reason, it’s sometimes referred to as MWC8222). It produces high-quality uniformly distributed pseudo-random numbers extremely quickly.

Here is a brief performance comparison between the statistics library, the mersenne-random library, the normal Haskell PRNG, and a C implementation of MWC256. The numbers represent millions of variates generated and summed per second, so higher is better. (Measured on a 64-bit Core2 Duo laptop running Fedora 11.)

Package Int64 Double Word32
System.Random 0.7 1.6 n/a
mersenne-random 101.2 53.8 96.3
statistics 145.7 116.5 251.6
C (normal) 131.0 103.2 292.9
C (inlined) 162.0 118.7 375.6
C (inlined, unrolled) 186.5 171.7 571.2

As the numbers indicate, the MWC256 implementation in the statistics library is up to 3 times faster than the mersenne-random library, and often faster than the C code you’d expect to encounter in practice. And you shouldn’t use the standard Haskell PRNG if you care about performance.

(The last two rows in the table above indicate what you could expect from an aggressive C compiler that performed cross-module inlining and loop unrolling, such as almost works reliably in gcc these days. If you were using normal compilation flags and source file structure, you would be unlikely to see those kinds of numbers in practice.)

A nice feature of the PRNG in the statistics library is that it has a cleaner interface than mersenne-random. Due to the cheesy implementation of the underlying C code, the mersenne-random library enforces the use of a single PRNG for the entire program, which makes it onerous to work with. You have to create a single generator when your program starts, and pass it everywhere that you might eventually need random numbers. In a multi-threaded program, only one thread at a time can use the PRNG.

The PRNG in the statistics library runs inside the ST monad, so you can generate random variates from inside pure Haskell code. You can create or use a generator anywhere without worrying about threading issues, and there’s a handy function provided that lets you seed a generator from your system’s random number source.

As a final tweak, the new PRNG generates floating point numbers in the range (0,1], so the variates it generates are safe for using in statistical computations that are zero-phobic, such as those involving logarithms or division. I’ve also included a generator for normally-distributed floating point numbers that uses Doornik’s modified ziggurat algorithm, so it’s both fast and trustworthy.

Posted in haskell, open source, science
5 comments on “A new pseudo-random number generator for Haskell
  1. brian says:

    That’s really cool! Thanks.

  2. Vermue says:

    Please try this prng.

    on

    http://www.number.com.pt/index.html

    Can you tell me the comparative results on it.

    Thank you

    Vermue

  3. PO8 says:

    I’ve used ISAAC as the underlying PRNG for generating normally-distributed variates via the Ziggurat method, since I haven’t found anything else robust enough to get a good distribution from this sensitive filter. I’ll give the PRNG you suggest a try and see what I find out. Sure would like to have a pure-Haskell ISAAC implementation, but that’s a hard one and I don’t think I’m up to it.

  4. Bart, the problem is that the ziggurat method as originally described and usually implemented is broken (see Doornik’s “An Improved Ziggurat Method to Generate Normal Random Samples” for an explanation). A less-than-stellar uniform PRNG merely makes the brokenness more obvious.

    My implementation uses a fast-and-good underlying PRNG and a better, but slower, ziggurat (Doornik’s), so it should equal or beat ISAAC-plus-broken-ziggurat on both performance and quality.

  5. Michael Lesniak says:

    Just wanted to thank you for this. Really nice!

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>