Subject: [Boost-bugs] [Boost C++ Libraries] #6135: Significant speed-up in gamma rng by switching from Knuth method to Marsaglia and Tsang (2000)
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2011-11-17 18:59:40
#6135: Significant speed-up in gamma rng by switching from Knuth method to
Marsaglia and Tsang (2000)
------------------------------------------------+---------------------------
Reporter: Jan Drugowitsch <jdrugo@â¦> | Owner: no-maintainer
Type: Patches | Status: new
Milestone: To Be Determined | Component: random
Version: Boost Development Trunk | Severity: Optimization
Keywords: gamma, rng |
------------------------------------------------+---------------------------
When compared to the GNU Scientific Library (GSL), the generation of
Gamma-distributed random numbers is very slow in Boost. A simple test,
generating 100000000 random numbers, reveals
GSL : 22.3233 MSamples/s[[BR]]
Boost : 5.41275 MSamples/s
where MSamples/s is million samples per second. The difference is due to
Boost using the Knuth method, whereas the GSL implements a newer method by
Marsaglia and Tsang (2000).
With the attached patch, which implements the newer method, the
performance improves to
GSL : 22.7472 MSamples/s[[BR]]
Boost : 14.5018 MSamples/s
The remaining difference between Boost and GSL can be traced back to GSL
using Zigguraut rather than Box-Muller to generate Normal random numbers.
At some point I might submit a patch for normal_distribution.hpp that
implements the Zigguraut algorithm.
The attached patch exactly follows gsl_ran_gamma of GSL v1.15
(gsl-1.15/randdist/gamma.c)
-- Ticket URL: <https://svn.boost.org/trac/boost/ticket/6135> Boost C++ Libraries <http://www.boost.org/> Boost provides free peer-reviewed portable C++ source libraries.
This archive was generated by hypermail 2.1.7 : 2017-02-16 18:50:07 UTC