Overflow while calculating combinations

Question

I am trying to calculate the combination C(40, 20) in C++, however the data types in C++ seems unable to correctly handle this calculation even though I have used long long data type. The following is my code:

#include <iostream>

long long fac(int x) {
    register long long i,f = 1; // Optimize with regFunction
    for(i = 1;i <= x;i++)
        f *= i;
    std::cout << f << std::endl;
    return f;
}

// C(n,r) = n!/r!(n-r)!
long long C(long long n, long long r) {
    return fac(n) / (fac(r) * fac(n - r));
}

int main(int argc, char const *argv[]) {
    std::cout << C(40, 20) << std::endl;
    return 0;
}

Any idea to solve this problem?

Answer 1

Compute C at once by executing division immediately after multiplication:

long long C(long long n, long long r) 
{
    long long f = 1; // Optimize with regFunction
    for(auto i = 0; i < r;i++)
        f = (f * (n - i)) / (i + 1);
    return f ; 
}

Result should be exact (divisions without remainders, until overflows) since any integer factor present in (i+1) is already present in (n -i). (Should not be too difficult to prove)