Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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...

share|improve this question
1  
This question might be better suited for scicomp.stackexchange.com . –  Emil Jeřábek Feb 8 '12 at 15:10
5  
Well, discussing a specific implementation might be better suited elsewhere, but a general discussion on algorithms seemed appropriate here. –  Julien Puydt Feb 8 '12 at 15:36
    
Does sage do better if you ask it to compute the beta function of the appropriate arguments? –  Igor Rivin Feb 9 '12 at 15:04
    
As I said, I'm more interested in discussing better algorithms than a specific implementation : I mostly wanted to explain why I came up with the question. And I'm not sure it has beta... and it's difficult to tell with such a name :-/ –  Julien Puydt Feb 9 '12 at 18:20
    
How about using the log-gamma function, and use subtraction instead of division? –  Luis Mendo Sep 30 '13 at 11:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.