mathematical calculations for larger values in c++

Question

It is a very simple program which have t test cases, and we have to find nCr=n!/r!*(n-r)!. So it works fine for smaller values like 20C2 but not for larger values lke 100C10. It gives 32C2=-6 ,100C10 floating point exception. how to make it for 1<=n<=r<=1000 ?? NOTE: I am not asking for long double or don't want to change it into float.Answer should be like 100C10 = 17310309456440 similarly 989C45=?

#include<iostream>
using namespace std;
long long int fact(long long int num);
int main()
{
int t;
cin>>t;
long long int n[1000],r[1000],c[1000];
for(int i=0;i<t;i++)
{
cin>>n[i];
cin>>r[i];
}
for(int i=0;i<t;i++)
{
c[i]=fact(n[i])/(fact(r[i])*fact(n[i]-r[i])) ;
cout<<c[i];
}
return 0;
}
long long int fact(long long int num){
long long int k;
if(num==0)
num=1;
else
{
for(k=num-1;k>0;k--)
num=num*k;
}
return num;
}

Answer 1

You have two options:

1. Use a multi precision library such as the one provided by Boost:

http://www.boost.org/doc/libs/1_53_0/libs/multiprecision/doc/html/boost_multiprecision/tut/ints/egs/factorials.html

2. When possible try to simplify the expression. This will work as long as your values are still small. Have a look at the numerator and denominator? Can you simplify something there? How are the values changing when you vary N and R? There are cases when one these partial results is smaller. Try to use that in your advantage.

Answer 2

Time for a touch of Maths:

nCr = fact(n)/(fact(r)*fact(n-r))

An example makes this easier, let's do 5C3:

5C3 = fact(5)/(fact(3)*fact(5-3))
    = fact(5)/(fact(3)*fact(2))
    = 5x4x3x2x1 / (3x2x1 * 2x1)
    = 5x4 / 2x1

So we can see that some of the factors will cancel; that is very useful if the full fact(n) would overflow.

Define a range factorial:

rafa(a,b) = a*(a-1)*...*(b+1)*b where a > b
          = product(b..a)

Then

rafa(n,r) = fact(n)/fact(r)
-> nCr = rafa(n,r) / fact(r)

We could stop here, and we would have significantly broadened the set of values of n and r for which we can calculate values without overflowing.

Extra points

With rafa(n,r) and fact(r), we can see that when r is nearly as large as n, then most of the scale of the problem will cancel. So 100C97 = 100x99x98 / 3x2x1 = 100x33x49.

Consider, then, a factor-matching algorithm (psuedo-code rather like python):

numerElems = [100,99,98]
initialDenomElems = [3,2,1]

# cancelFactors modifies numerElems values, returns un-cancelled denominator elements
def cancelFactors(numerElems, denomElems):
    finalDenomElems = []
    for denom in denomElems:
        for factor in factorise(denom):
            for idx,numer in enumerate(numerElems):
                if isFactorOf(factor, numer):
                    numerElems[idx] = numer/factor
                else
                    finalDenomElems.push(factor)
    return finalDenomElems;

You can then perform the final calculation of the product of the numerator elements divided by the product of the remaining denominator elements. Since we know nCr always returns an integer result, we know that when cancelFactors is used it will always cancel all the factors. Thus this algorithm maximises the possible space of n,r pairs which do not overflow. However, as written, it is O(n^3 * f), where f is the cost of getting all the factors of an integer, so it will not be fast. For large values of n and r, though, it may be the only way to calculate the result without using different types.