[random] normal_distribution, cartesian form of box-muller transform
Hello, I have adapted the current normal_distribution from the polar form to the outward Cartesian form. See here http://web.mat.bham.ac.uk/marijke/bm/yabm.pdf listing the benefits of the Cartesian form for the distribution of numbers. This also eliminates trigonometric function calls, however, it does reject pairs of random numbers. Most websites (wolfram, wikipedia) state that the inward Cartesian form is faster but this is generator speed dependent. I've found with my tests (mt19937, double datatype, gcc (GCC) 4.1.3 20070929 (prerelease) (Ubuntu 4.1.2-16ubuntu2), -O2) its about 1.5x slower than the polar form. Although with faster generators I expect it to outperform the polar version. I think this is an improvement on the current normal_distribution.hpp in time critical situations (if a fast generator is used) and it gives a better distribution of numbers, (points rather than bands of inaccessible numbers). I have also found that this version doesn't produce the "may be used uninitialised" warning when compiling with optimisations that I get when I use the original. Please let me know if you think of any other improvements or spot any errors. I will use this in my code however I would like to give something back. I'm not sure what to do with the copyright at the top of the file and I'm not sure if this is the correct way to submit this for review. Apologies in advance if I have made a mistake. Marcus Bannerman
-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Marcus Bannerman Sent: 12 November 2007 08:44 To: boost@lists.boost.org Subject: [boost] [random] normal_distribution,cartesian form of box-muller transform
Hello, I have adapted the current normal_distribution from the polar form to the outward Cartesian form. See here http://web.mat.bham.ac.uk/marijke/bm/yabm.pdf listing the benefits of the Cartesian form for the distribution of numbers. This also eliminates trigonometric function calls, however, it does reject pairs of random numbers. Most websites (wolfram, wikipedia) state that the inward Cartesian form is faster but this is generator speed dependent.
I've found with my tests (mt19937, double datatype, gcc (GCC) 4.1.3 20070929 (prerelease) (Ubuntu 4.1.2-16ubuntu2), -O2) its about 1.5x slower than the polar form. Although with faster generators I expect it to outperform the polar version.
I think this is an improvement on the current normal_distribution.hpp in time critical situations (if a fast generator is used) and it gives a better distribution of numbers, (points rather than bands of inaccessible numbers). I have also found that this version doesn't produce the "may be used uninitialised" warning when compiling with optimisations that I get when I use the original.
Please let me know if you think of any other improvements or spot any errors. I will use this in my code however I would like to give something back.
This sounds a clear improvement but I'm not sure how to suggest it should be incorporated into future releases. At the very least you should put it in the Boost sandbox with a covering text file?
I'm not sure what to do with the copyright at the top of the file.
You should simply add your own line Copyright Marcus Bannerman 2007 underneath the existing copyright to read thus " Copyright Jens Maurer 2000-2001 Copyright Marcus Bannerman 2007 Distributed under the Boost Software License, Version 1.0. It might help also to add you initials to the revision history line?... " HTH Paul --- Paul A Bristow Prizet Farmhouse, Kendal, Cumbria UK LA8 8AB +44 1539561830 & SMS, Mobile +44 7714 330204 & SMS pbristow@hetp.u-net.com
Paul A Bristow wrote:
Please let me know if you think of any other improvements or spot any errors. I will use this in my code however I would like to give something back.
This sounds a clear improvement but I'm not sure how to suggest it should be incorporated into future releases. At the very least you should put it in the Boost sandbox with a covering text file?
Right, and open a Track issue at svn.boost.org with "random" as the compoment: we currently have a bit of backlog of random lib issues, and a maintainer that's AWOL/busy, but hopefully someone will go through and clear the issues out at some point ! HTH, John.
In case anyone searches the archive for box-muller, or normal distribution, as I did, I've posted the final file (and will post improvements) in the tracker at http://svn.boost.org/trac/boost/ticket/1437 Marcus On Nov 12, 2007 5:15 PM, John Maddock <john@johnmaddock.co.uk> wrote:
Paul A Bristow wrote:
Please let me know if you think of any other improvements or spot any errors. I will use this in my code however I would like to give something back.
This sounds a clear improvement but I'm not sure how to suggest it should be incorporated into future releases. At the very least you should put it in the Boost sandbox with a covering text file?
Right, and open a Track issue at svn.boost.org with "random" as the compoment: we currently have a bit of backlog of random lib issues, and a maintainer that's AWOL/busy, but hopefully someone will go through and clear the issues out at some point !
HTH, John.
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
participants (3)
-
John Maddock -
Marcus Bannerman -
Paul A Bristow