CODEWITHSUNDEEP
c++binomial-coefficients
user1751550
user1751550

Reputation: 85

binomial coefficient

I have a code which calculate binomial coefficient, but when number is bigger then 20, it start to calculate wrong, where is the problem? Thanks

#include <iostream>
using namespace std;

long int bin(long int x)
{
    if(x==0)
        return 1;
    long int r = x;
    for(int i = r-1;i>0;i--)
    {
        r = r*i;
    }
    return r;
}
int main()
{
    cout << "Write n and k: " << endl;
    long int n=0;
    long int k=0;
    cin >> n;
    cin >> k;
    long int result = 0;
    long int fn = bin(n);
    long int fk = bin(k);
    long int fnk = bin(n-k);


    result = fn/(fk*fnk);

    cout << endl << "C = " << result << endl;


    return 0;
}

for example 12 and 5 = 792 which is correct, but 20 and 4 = -2 which is not correct

Upvotes: 0

Views: 6737

Answers (3)

Anirudh Ramanathan
Anirudh Ramanathan

Reputation: 46728

You are calculating the factorial of n using

bin(n);

You are running past the limit of long when n is >=20.

As @SteveJessop pointed out in the comments, You would overrun the limit even if you used unsigned long long (the longest fixed-point type) which has a range from 0 to 18446744073709551615

You could use an int-array to store your result as detailed here.

Upvotes: 2

Yakov Galka
Yakov Galka

Reputation: 72449

20! = 2432902008176640000, which is far beyond what long int can hold (typically 2147483647). Use double instead.

Upvotes: 2

Steve Jessop
Steve Jessop

Reputation: 279195

Your bin function computes the factorial. The factorial of 21 doesn't fit in a long.

You're already relying on an implementation detail. long is only required to be 32 bits, but on your system it's 64. If it were only 32, then you'd fail much sooner.

Upvotes: 2

Related Questions