Integer calculation of the binomial coefficient using boost::math::binomial_coefficient, returning value as boost::multiprecision::cpp_int? How?

Question

I would like to calculate the binomial coefficient as an integer for up to about numberLeaves=100, K=10. I believe this should be possible to store in about a 128 bit integer.

Therefore, I'd like to use boost::multiprecision::cpp_int to store the result, and use boost::math::binomial_coefficient<boost::multiprecision::cpp_int> to calculate it:

// Invalid because the template argument must be a floating-point type!
boost::multiprecision::cpp_int number_branch_combinations = 
    boost::math::binomial_coefficient<boost::multiprecision::cpp_int>(numberLeaves, K);

Unfortunately, even though the binomial coefficient is an integer, the above code is invalid because boost::math::binomial_coefficient requires that the return value must be a floating point type, claiming that:

...the template argument must be a real-valued type such as float or double and not an integer type - that would overflow far too easily!

As noted, in my case I expect the result of the binomial coefficient calculation to fit within about 128 bits - and I'd like it as an integer.

Therefore, I considered passing boost::multiprecision::cpp_dec_float as the template argument to boost::math::binomial_coefficient, and then doing a conversion from the floating-point return value (via rounding) to the nearest integer.

Sadly, I can find no way to convert from a boost::multiprecision::cpp_dec_float to a boost::multiprecision::cpp_int. It seems that performing a lossy conversion is strictly prohibited by the boost::multiprecision library:

cpp_int             cppi(2);
cpp_dec_float_50    df(cppi);    // OK, int to float
df                  = static_cast<cpp_dec_float_50>(cppr);  // OK, explicit rational to float conversion
// However narrowing and/or implicit conversions always fail:
cppi                =   df;    // Compiler error, conversion not allowed

Now I'm in the process of simply writing my own function to calculate the binomial coefficient, and return the value as an integer.

I find it hard to believe that there is literally no possible way to use boost::math::binomial_coefficient to calculate the binomial coefficient and return it as a boost::multiprecision::cpp_int.

Is it possible to use boost::math::binomial_coefficient to calculate the binomial coefficient and return it as a boost::multiprecision::cpp_int?

Answer 1

I find it hard to believe that there is literally no possible way to use boost::math::binomial_coefficient to calculate the binomial coefficient and return it as a boost::multiprecision::cpp_int.

Why do you think it's so hard to believe?

It was a clear design choice, has been documented as such, and it made very much sense at the time.

Boost Multiprecision got introduced in 1_53 only. I think the binomial_coefficient is easily years older than that (though I haven't checked).

So, instead of expressing your disgust, you should probably be talking to the devs at the boost mailing lists to suggest this new feature. Boost library maintainers are usually quite eager to integrate with (new) libraries.

As you'll realize, you can wrap the function for now, doing the conversion. It's faaar from ideal, but it's less work than supplying the patch for Boost Math yourself :)

Answer 2

Here's what I use to get total number of n choose k:

boost::multiprecision::cpp_int BinomialCoefficient(unsigned int n, unsigned int k) {
  if (k == 0) { return 1; }
  else { return (n * BinomialCoefficient(n - 1, k - 1)) / k; }
}

This was adapted from this answer and I gotta say it's done me well.