How to evaluate binomial coefficients efficiently and as correctly as possible?

2012-02-08T14:58:17Z

This question is more precisely about evaluation with a computer, of a binomial coefficient of the form $ \binom{x}{m}$ where $x$ is a real number and $m$ a rational integer.

The reason why I ask is that I found out recently that sage is using the naive definition with the $\Gamma$ function, which means that it gets as a result NaN (not-a-number) with quite small parameters, for which the real result is pretty reasonable and should have been given (see the bug report).

I have proposed to change the implementation by returning zero in more cases than it already does, to reduce to a situation $\binom{x}{m}$ with $x\geq m\geq 0$, so we can write $x=m+k+u$ with $k$ a natural integer and $u\in[0;1[$, then computing the quotient $\Gamma(x+1)/\Gamma(m+1)$ with a Pochhammer symbol times the quotient $\Gamma(m+1+u)/\Gamma(m+1)$. For that last quotient, I was proposing a direct computation for small $m$ and a polynomial expansion in $u$ for big $m$.

There are two problems with this approach:

I don't really know how big the error is, which for a numerical computation is a pretty big issue ;
I used the naive code as a starting point, and added naive ideas to the mix : there may exist better approaches (it's also because of this point that I didn't try to evaluate the error more precisely).

It would be surprising if there existed no algorithm for this kind of computations, given how important those coefficients are in various situations...

How to evaluate binomial coefficients efficiently and as correctly as possible? - MathOverflow

How to evaluate binomial coefficients efficiently and as correctly as possible?