[Boost-bugs] [Boost C++ Libraries] #6135: Significant speed-up in gamma rng by switching from Knuth method to Marsaglia and Tsang (2000)

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.