Explanation for calculating ncr

Question

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

Which is better way to calculate nCr

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?

Answer 1

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.