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
16 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. A Greek chorus of historical figures, including Leonardo da Vinci and 19th-century politician Giuseppe
    Garibaldi, add rueful comment on the characters and their troubles while arguing about Italy’s distressing current state
    of affairs. It would be a dream come true, partying with the
    cartoon character voted the 2nd most influential in history.
    An electronic board alerting moviegoers when their show is starting and when it’s time
    for seating for that particular show, is situated in the lounge, as is
    a large HDTV.

    my webpage – Grace de Monaco Télécharger

  7. We’re a group of volunteers and opening a new scheme in our community.
    Your web site provided us with valuable info to work on. You’ve done an impressive process and our entire neighborhood might be grateful to you.

  8. Lacy says:

    Wow, this paragraph is fastidious, my younger sister is analyzing these kinds of
    things, therefore I am going to inform her.

  9. This is really interesting, You are a very skilled blogger.

    I have joined your feed and look forward to seeking more of your fantastic post.
    Also, I have shared your web site in my social networks!

  10. What’s up, I log on to your new stuff regularly.
    Your writing style is witty, keep it up!

  11. The zoo is easily found and has plenty of parking space.

    After our meal and resting awhile we decided to call it a
    day. A one-hour guided historical walk on Shell Island Road
    to see an ancient shell mound also is offered to groups.

    Here is my blog; hud homes for sale (http://en.calameo.com/read/003517714ad3248caa31d)

  12. Hey there! I just wanted to ask if you ever have any issues with hackers?

    My last blog (wordpress) was hacked and I ended up
    losing a few months of hard work due to no backup. Do you
    have any solutions to stop hackers?

  13. I loved as much as you will receive carried out right here.
    The sketch is tasteful, your authored subject matter stylish.
    nonetheless, you command get got an shakiness over that you wish be delivering the following.
    unwell unquestionably come further formerly again since exactly the same
    nearly very often inside case you shield this increase.

  14. We’ve been several volunteers as well as establishing the latest system within our area. Your blog offered you together with handy information and facts to function upon. You’ve performed some sort of powerful activity and also the full town would be fortunate for you.

  15. kids arts says:

    This post gives clear idea for the new viewers of blogging,
    that truly how to do running a blog.

    kids arts

  16. If you want a smaller but higher quality picture then a Plasma TV would be a good option as these can be purchased at sizes up to 65 inches,
    and therefore still providing you with a big screen viewing experience.

    The rally and passing of Resolution 1010 pave the way
    for proposing House Bill 1286, which will double the incentives offered by the state to attract
    more film, TV, and media productions. There are several cinema news website which update the photos and videos of
    the wedding.

    Feel free to visit my blog: Sin City j’ai tué pour elle Télécharger

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>