[Boost-bugs] [Boost C++ Libraries] #1540: Poisson distribution very slow for large mean (and may also overflow).

Subject: [Boost-bugs] [Boost C++ Libraries] #1540: Poisson distribution very slow for large mean (and may also overflow).
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2007-12-27 10:17:10

#1540: Poisson distribution very slow for large mean (and may also overflow).
--------------------------+-------------------------------------------------
 Reporter:  johnmaddock   |       Owner:  jsiek  
     Type:  Bugs          |      Status:  new    
Milestone:  Boost 1.36.0  |   Component:  None   
  Version:  Boost 1.34.1  |    Severity:  Problem
 Keywords:                |  
--------------------------+-------------------------------------------------
 Joel Eidsath reports:

 The poisson_distribution code will fail for any mean larger than 750
 or so (on my x86_64 machine). The problem is a comparison with
 exp(-_mean) which evaluates as zero right around there.

 The easiest fix is to operate with logs instead of exponents. I
 changed the operator() code to be something like this:

 RealType product = RealType(0);
     for(result_type m = 0; ; ++m) {
       product += log(eng());
       if(product <= -_mean)
         return m;
     }

 This also makes it possible to get rid of the init() function and the
 _exp_mean private member variable.

 A far better fix would be to use an algorithm other than Knuth's for
 this. Knuth's algorithm is simple, but O(n).

 References to better implementation methods include:

 * Numerical Recipes
 * http://statistik.wu-wien.ac.at/unuran

 * "Non-Uniform Random Variate Generation" by Luc Devroye. Full text
 available for free at http://cg.scs.carleton.ca/~luc/rnbookindex.html with
 Poisson covered in chapt 10 at
 http://cg.scs.carleton.ca/~luc/chapter_ten.pdf starting p501.

-- 
Ticket URL: <http://svn.boost.org/trac/boost/ticket/1540>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.