How to evaluate binomial coefficients efficiently and as correctly as possible? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T23:20:17Z http://mathoverflow.net/feeds/question/87898 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/87898/how-to-evaluate-binomial-coefficients-efficiently-and-as-correctly-as-possible How to evaluate binomial coefficients efficiently and as correctly as possible? Julien Puydt 2012-02-08T14:58:17Z 2012-02-08T14:58:17Z <p>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.</p> <p>The reason why I ask is that I found out recently that <a href="http://www.sagemath.org" rel="nofollow">sage</a> 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 <a href="http://trac.sagemath.org/sage_trac/ticket/12448" rel="nofollow">bug report</a>).</p> <p>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$.</p> <p>There are two problems with this approach:</p> <ul> <li>I don't really know how big the error is, which for a numerical computation is a pretty big issue ;</li> <li>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).</li> </ul> <p>It would be surprising if there existed no algorithm for this kind of computations, given how important those coefficients are in various situations...</p>