I received a Ph.D. in number theory from UC Berkeley in 1997. I also enjoy other areas of math, as well as physics and computer programming. I live in Goleta, CA, near Santa Barbara and work at Raytheon in Goleta.

Sorry. I think Herbert completely misunderstands the issue. In fact, he seems to be wrong on all counts.

It DOES have an overflow issue, just as as nchoosek has an issue. For example,

>> nchoosek(1500,265)
Warning: Result may not be exact. Coefficient is greater than 9.007199e+15 and is only accurate to 15 digits
> In nchoosek at 92
ans =
1.58269376513703e+302

nchoosek does return a valid answer, WITH a warning that it is not exact. But since the result has 303 decimal digits and is returned as a double what do you expect???

binomial also returns the same thing, however it generates no warning message. That does not say it has no issue, only that it fails to be friendly and warn you of that fact!

Both codes will return inf when the arguments cause a double to be exceeded.

binomial(1500,275)
ans =
Inf

However, note that nchoosek is both more flexible and more powerful than is binomial. And nchoosek has been around since the dark ages. So the fact that David could not find it is merely a reflection that he did not look that hard. Jos points out the simple use of lookfor that would have given him the answer.

nchoosek also has the ability to give exact results for a slightly larger set of inputs than binomial. So if the input is uint64, so will be the output.

Here nchoosek was exact, whereas binomial was wrong. In fact, nchoosek CAN do symbolic computation, whereas binomial fails to return anything of value.

>> binomial(sym(1500),30)
ans =
exp(gammaln(1501) - gammaln(1471) - 5253606334386405/70368744177664)

Of course, nchoosek even works perfectly for vpi input, whereas binomial fails there completely.

There is only one point made by Herbert that MIGHT be correct in some circumstances, i.e., that binomial is faster. Since binomial does no error checking and it has lesser capability than does nchoosek, of course it might be faster. On top of that, the gamma log computation for large input might be be pretty fast. But is it good? Even for double inputs...

>> binomial(101,10)
ans =
19212541264839.3

>> nchoosek(101,10)
ans =
19212541264840

Oops. I'm pretty sure that most binomial coefficients are integers, at least they were when I went to school. You never know with the new math though. But I would think it disappointing to see a floating point result that is not a pure integer, at least for a reasonably small set of inputs.

So how about speed. Is it faster? I'll use timeit to do the comparison.

>> timeit(@() nchoosek(100,10))
ans =
8.32913416666667e-05

>> timeit(@() binomial(100,10))
ans =
0.0002867962125

So here nchoosek was actually 4 times FASTER than binomial. Not slower. binomial is the slow one.

08 Apr 2014

binomial.m
This program computes the binomial coefficient C(n,m).
Author: David Terr