CODEWITHSUNDEEP
c++
soc5
soc5

Reputation: 9

Binomial coefficient programm outputs wrong results, if inputs are large(C++)

I have created a programm, that calculates binomial coefficient:

#include <iostream>
#include <string>
using namespace std;

int factorial(int num){
    int res = 1;
    for(int i = 1;i <= num; ++i){
        res *= i;
    }
    return res;
}

int binom(int n,int k){
    int factorial(int num);
    int binom_coef;
    binom_coef = factorial(n)/(factorial(k)*factorial(n-k));
    return binom_coef;
}

int main(){
    int n,k;
    int binom(int n,int k);
    try{
        cout << "Enter number n:";
        cin >> n;
        cout << "Enter number k:";
        cin >> k;
        if(n < k){
            throw -1;
        }
        cout << binom(n,k) << "\n";

    }catch(int x)
        cout << "n must be biggger than k";

}

For small inputs(up to 10) everything works perfectly fine. But if I enter big enough n and k(more than 10) the calculations are totally wrong and I cannot figure out why is that.

Can you help me?

Upvotes: 0

Views: 50

Answers (1)

NYG
NYG

Reputation: 1817

The factorial is a function that grows really fast. It may be that for n > 10 your factorials already overflow the int type.

In fact, 12! = 479001600

You’re applying the theoretical formula for the binomial coefficient, but if you try the operative definition you may have less problems:

10 : 2 = 10! / (2! * 8!) = (10 * 9) / (2 * 1)

So what you can do is: multiply all numbers in [n, n - k), then divide them for all the numbers in [k, 1).

int bin_coeff(int n, int k) {
   int res = 1, i = n;
   while (i > n - k)  res *= i--;
   while (i > 0)  res /= i--;
   return res;
}

As you can see, you’ll calculate 10 : 2 by simply doing 90 / 2, which are not big numbers, and you’ll even get a better efficiency for your algorithm.

Upvotes: 1

Related Questions