C++ Binomial Coefficient is too slow

Question

I've tried to compute the binomial coefficient by making a recursion with Pascal's triangle. It works great for small numbers, but 20 up is either really slow or doesn't work at all.

I've tried to look up some optimization techniques, such as "chaching" but they don't really seem to be well integrated in C++.

Here's the code if that helps you.

int binom(const int n, const int k)
{
    double sum;

    if(n == 0 || k == 0){
            sum = 1;
    }
    else{
    sum = binom(n-1,k-1)+binom(n-1,k);
    }

    if((n== 1 && k== 0) || (n== 1 && k== 1))
       {
           sum = 1;
       }
    if(k > n)
    {
        sum = 0;
    }

    return sum;

}

int main()
{
int n;
int k;
int sum;

cout << "Enter a n: ";
cin >> n;
cout << "Enter a k: ";
cin >> k;

Summe = binom(n,k);

cout << endl << endl << "Number of possible combinations: " << sum << 
endl;

}

My guess is that the programm wastes a lot of time calculating results it has already calculated. It somehow must memorize past results.

Answer 1

My guess is that the program wastes a lot of time calculating results it has already calculated.

That's definitely true.

On this topic, I'd suggest you have a look to Dynamic Programming Topic.

There is a class of problem which requires an exponential runtime complexity but they can be solved with Dynamic Programming Techniques. That'd reduce the runtime complexity to polynomial complexity (most of the times, at the expense of increasing space complexity).

---

The common approaches for dynamic programming are:

• Top-Down (exploiting memoization and recursion).
• Bottom-Up (iterative).

Following, my bottom-up solution (fast and compact):

int BinomialCoefficient(const int n, const int k) {
  std::vector<int> aSolutions(k);
  aSolutions[0] = n - k + 1;

  for (int i = 1; i < k; ++i) {
    aSolutions[i] = aSolutions[i - 1] * (n - k + 1 + i) / (i + 1);
  }

  return aSolutions[k - 1];
}

This algorithm has a runtime complexity O(k) and space complexity O(k). Indeed, this is a linear.

Moreover, this solution is simpler and faster than the recursive approach. It is very CPU cache-friendly.

Note also there is no dependency on n.

I have achieved this result exploiting simple math operations and obtaining the following formula:

(n, k) = (n - 1, k - 1) * n / k

Some math references on the Binomial Coeffient.

---

Note

The algorithm does not really need a space complexity of O(k). Indeed, the solution at i-th step depends only on (i-1)-th. Therefore, there is no need to store all intermediate solutions but just the one at the previous step. That would make the algorithm O(1) in terms of space complexity.

However, I would prefer keeping all intermediate solutions in solution code to better show the principle behind the Dynamic Programming methodology.

Here my repository with the optimized algorithm.