Opened 7 years ago

#6135 new Patches

Significant speed-up in gamma rng by switching from Knuth method to Marsaglia and Tsang (2000)

Reported by: Jan Drugowitsch <jdrugo@…> Owned by: No-Maintainer
Milestone: To Be Determined Component: random
Version: Boost Development Trunk Severity: Optimization
Keywords: gamma, rng Cc:


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
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
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)

Attachments (1)

gamma_distribution.patch (5.3 KB) - added by Jan Drugowitsch <jdrugo@…> 7 years ago.

Download all attachments as: .zip

Change History (1)

Changed 7 years ago by Jan Drugowitsch <jdrugo@…>

Attachment: gamma_distribution.patch added
Note: See TracTickets for help on using tickets.