[Boost-bugs] [Boost C++ Libraries] #9652: Infinite loop in random::binomial_distribution

Subject: [Boost-bugs] [Boost C++ Libraries] #9652: Infinite loop in random::binomial_distribution
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2014-02-11 04:06:04

#9652: Infinite loop in random::binomial_distribution
-------------------------------------------------+-------------------------
 Reporter:  Nobuto Takeuchi <takeuchi.nobuto@…>  |      Owner:  no-
     Type:  Bugs                                 |  maintainer
Milestone:  To Be Determined                     |     Status:  new
  Version:  Boost Development Trunk              |  Component:  random
 Keywords:                                       |   Severity:  Problem
-------------------------------------------------+-------------------------
 There is a potential infinite loop in binomial_distribution::invert(). The
 problem is caused by round-off errors. The condition required for the
 infinite loop is:

 t (no. trials) is large[[BR]]
 p (probability) is small[[BR]]
 uniform_01 returns a number very close to 1.[[BR]]


 I found this problem in Boost 1.48.0, but the relevant part of the code is
 the same in development trunk.


 The issue can be reproduced by the following program.
 {{{
 #include <iostream>
 #include "boost/random/binomial_distribution.hpp"

 /* PSEUDO uniform random number generater. */
 class URNG {
 public:
   typedef unsigned long int result_type;
   result_type operator()() {return _ret_val;}
   result_type min() const {return 0;}
   result_type max() const {return
 std::numeric_limits<result_type>::max();}
   URNG(result_type ret_val) :
     _ret_val(ret_val)
   {}
 private:
   result_type _ret_val;
 };

 int main(void)
 {
   typedef boost::random::binomial_distribution<long int, double> Binom;
   Binom binom(41344,4.87026e-05);

   URNG urng_small(1024);
   std::cout << "Draw a number from a binomial distribution." << std::endl;
   std::cout << "binom returns " << binom(urng_small) << std::endl;

   URNG urng_big(std::numeric_limits<unsigned long int>::max() - 1024);
   std::cout << "Draw again a number from a binomial distribution." <<
 std::endl;
   std::cout << "binom does not return (infinite loop) " << binom(urng_big)
 << std::endl;

   return 0;
 }
 }}}

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