Explanation for calculating ncr

Question

I was reading the possible efficient methods for calculating ncr when I came across this post.

The second answer given here, an I'm not able to understand that. The code is:

long long combi(int n,int k)
{
    long long ans=1;
    k=k>n-k?n-k:k;
    int j=1;
    for(;j<=k;j++,n--)
    {
        if(n%j==0)
        {
            ans*=n/j;
        }else
        if(ans%j==0)
        {
            ans=ans/j*n;
        }else
        {
            ans=(ans*n)/j;
        }
    }
    return ans;
}

And what will be the complexity for this? I tried doing it with an example and the answer comes out right but what are those conditions?

score 0 · Answer 1 · answered Oct 03 '14 at 07:46

As state in the link, the multiple condition in the loop is to handle overflow when doing ans = (ans * n) / j.

So the function is:

long long ans = 1;
k = std::min(k, n-k);
int j = 1;
for (; j <= k; j++, n--) {
    ans = (ans * n) / j;
}
return ans;

We have C(n, r) = n! / (n-r)! r! and most factors can be simplified.

And the complexity is k.

score 0 · Accepted Answer · answered Oct 03 '14 at 07:56

that is just the result of optimisations, it computes

n! / k! (n-k)! = n * (n-1) * ... (n - k + 1) / k * (k-1) * ... * 1

First : algorithmic optimisation : as C n k = C n (n-k) : compute the one that has less terms - nice.

Next computations optimisations : when computing ans * n / j try to simplify the fraction before doing the operation - IMHO this one is highly discutable because it is the way a human would do (you and I compute faster 6 / 3 than 12345678 / 9) but for the processor, this optimisation just add superfluous operation.

Explanation for calculating ncr

2 Answers2