binomfactors

Returns a factored form for very large binomial coefficients

Every once in a while someone wishes to compute a VERY large binomial coefficient. While I'll admit that most of the time the proper solution is to compute the log of the coefficient. The best solution for this is to use gammaln.

n = 20000000;
k = 5000000;
gammaln(n+1) - gammaln(k+1) - gammaln(n-k+1)
ans =
11246694.4048045

Once in a rare while someone might wish to compute the integer factors of this coefficient. I've now had two recent occasions to look for such a factorization, so I assume there must be someone else in the world who has a use for them too.

tic,[facs,count] = binomfactors(20000000,5000000);toc
Elapsed time is 43.071204 seconds.

We can verify the result by computing the log of the binomial coefficient from the factors. See that it is identical to that returned from gammaln above.

sum(log(facs).*count)
ans =
11246694.404804

How many digits are in this number?

sum(log(facs).*count)/log(10)
ans =
4884377.31965857

I did say it was large, with approximately 4.8 million digits.

So, for that rare person who wishes to compute the factors of a binomial coefficient, binomfactors does exactly that. Or, if all you wish to see are some ideas on how one might design a prime sieve for such a computation in MATLAB, this might be of some interest.

(Note that while this tool is used in my vpi toolbox, it does not require vpi to run.)