Fast Evaluation of Multiple Binomial Coefficients

Question

Suppose we have a sequence of binomial coefficients.

$$ S = \left\langle \binom{5}{2}, \binom{5}{3}, \binom{6}{3}, \binom{17}{14}, \binom{19}{15} \right\rangle $$

How can we efficiently evaluate all of them, minimising redundant computations? In this case

$$ S = \langle 10, 10, 20, 680, 3876 \rangle. $$

Admittedly, I do not know much about fast multipoint polynomial evaluation, but this question seems easier because it relies only on multiplicative structure (factorials). Also, I am aware of Kummer's theorem, but not sure how to effectively utilise it for this problem.

---

As a bonus question, how can we efficiently find the sum of a given sequence of binomial coefficients? Using the above example we would obtain

$$ \Sigma S = 2 \binom{6}{3} + \frac{67}{10} \binom{17}{3} = 4596. $$

There are various identities that help in special cases, but is there a more general method?

---

If these questions are still too difficult to answer exactly, then I am also interested in efficient approximation/convergence methods.

Answer 1

I am not a mathematician, but I am an experienced software engineer. I think you could use some techniques to make this evaluation faster. Here are a few tips:

Reduce the number of multiplications

Consider the evaluation of a binomial coeficient:

$$ \binom{n}{k} = \frac{n!}{k! (n-k)!} $$ Slow: $$ \binom{17}{14} = \frac{17!}{14!\;3!} = \frac{17!}{14!\;3!} = \frac{17\cdot16\cdot15\cdot14\cdot13\cdot12\cdot11\cdot10\cdot9\cdot8\cdot7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1}{(14\cdot13\cdot12\cdot11\cdot10\cdot9\cdot8\cdot7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1)\cdot(3\cdot2\cdot1)} = 680 $$ Fast: $$ \binom{17}{14} = \binom{17}{3} = \frac{17\cdot16\cdot15}{3\cdot2\cdot1} = 680 $$ So the optimization tips are:

1. The evaluation of a binomial coefficient can be done with ($n-k$) numbers in the numerator and denominator. In the example above, we can compute $\binom{17}{14}$ with just three numbers ($n - k = 17 - 14 = 3$) in the numerator and denominator.
2. Choose the smallest denominator possible. As seen in the example above, $\binom{17}{14}$ = $\binom{17}{3}$. Since $3 < 14$, it is easier to compute $\binom{17}{3}$ because it will be three multiplications in the numerator and three in the denominator. In other words, the denominator will be $3!$ and the numerator will be the first $3$ terms of $17! = 17 \cdot 16 \cdot 15$.

Cache the results

Caching the results (also called Memoization) can bring significant performance improvements to your algorithm. For each range of multiplications you have to calculate, cache the results!

Imagine that you have to calculate $4! = 24$, so you save this information in your cache. If you then have to calculate $6!$, remember that $6! = 6 \cdot 5 \cdot 4!$. There is no need to recalculate $4!$ because you already have the results.

You should also cache the result of the binomial coefficients and their complements. For example, if you calculate $\binom{17}{3}$, you should also cache $\binom{17}{14}$.