Infinite loop in random::binomial_distribution

[Nobuto Takeuchi <takeuchi.nobuto@…>]

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
p (probability) is small
uniform_01 returns a number very close to 1.

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;
}

[Steven Watanabe]

Fixed in ​http://github.com/boostorg/random/commit/9cd247da37bd9b13c06956c4d3901376f0e00722.