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
11 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!

  6. Theeb says:

    We also have a love hate relation with some trees only ours are 60 foot pines. Our view has been solwly diminishing over the years so last fall we took out a few selected trees. Big decision though as the pine beetle is going through pretty good here and they are not as selective as we are. Las thing we need to do is end up with no trees in the front which would open us up to the road. You are best to go slow.

  7. 海淘 says:

    This piece of writing will assist the internet
    people for building up new webpage or even a weblog
    from start to end.

  8. Cortez says:

    I’m not a big Spruce fan (way too prickly) but if you sutistbute in Doug Firs or Hemlocks, I completely understand. One of the hardest things we did when we moved into our house was cut all the overgrown cedars and shrubs down. It was necessary, even if it meant the weeds moved right in, but we still haven’t had the time or money to fill in all the vacated space with things that we really want.

  9. I had no idea how to approach this before-now I’m locked and loaded.

  10. Of course, in this story, we’re assuming that sovereign states have the right to restrict movement of people across their borders and impose ever more intrusive and insolent tests they have to submit to. The point where large numbers of people start to boycott countries like Japan or the US for engaging in these practices, is where things will start to get interesting.

  11. HenrikI did not mean to accuse YOU of Newspeak. But the “Spiegel” for instance reports “amateur electrical installation” today. And that is surely not a euphemism.”That’s something I use to leave an obvious conclusion up to the reader, so as to make that conclusion his own, not something pushed on him from the outside. It’s a sublte art”Hey, you will forgive me for not catching subtleties. You know how literal us Krauts are …

Leave a Reply

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

*