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;
}

You'll need arbitrary-length integers. There's nothing built into the language, so you'll need to do it yourself (storing the large number in an array of smaller values and writing a functions to multiply and print them) or use a library like [GMP](https://gmplib.org/) — Mike Seymour, Nov 21 '14 at 10:53
You can get rid of the factorials and avoid overflow by summoning the Ancient Power of Mathematics. — molbdnilo, Nov 21 '14 at 11:01
No standard type will fit 1000C500 whether unsigned or signed. — Ivaylo Strandjev, Nov 21 '14 at 11:10
I don't understand why this is a duplicate. Using a multi precision library like boost should be considered if you want to extend the range of your answer, regardless of how you simplify the expression. — Juan Leni, Nov 24 '14 at 19:29

Phil H · Answer 1 · 2014-11-21T12:40:58.427

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.

But however cunning you are mathematically, 1000C500 is still far to large for any C++ type to represent exactly (2.7e299, according to some random online calculator I found, which needs almost a thousand bits). You'll need something else to support the whole range 1<=n<=r<=1000. — Mike Seymour, Nov 21 '14 at 13:36
And Mr @spektre if you can't get the question please don't mark it duplicate . I am not asking for a better way of same program , I can optimize it. — Kushagra Sharma, Nov 21 '14 at 13:44

Juan Leni · Answer 2 · 2014-11-21T11:18:05.480

You have two options:

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

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.

mathematical calculations for larger values in c++

2 Answers2