Newton biomial - doesn't work for large numbers
I wrote a program that should print the value of Newton's binomial. - the number of tests t[i][0] - n
, t[i][1] - k
. This seems to be ok for small numbers n and k, but when I want to print large numbers, it prints 0
, 1
or a small negative integer. I mainly used long int int so that it works with large numbers. Could you explain why?
#include <iostream>
long fact(int x);
using namespace std;
int main()
{
int number;
cin>>number;
int t[number][2];
for(int i=0; i<number; i++)
{
cin>>t[i][0];
cin>>t[i][1];
if (t[i][0]<t[i][1]) return 0;
}
for(int i=0; i<number; i++)
{
cout<<fact(t[i][0])/(fact(t[i][0]-t[i][1])*fact(t[i][1]))<<endl;
}
return 0;
}
long fact(int x)
{
long factt=1;
for(int i=1; i<=x; i++)
{
factt=factt*i;
}
return factt;
}
@edit
Thanks for the advice. I tried to implement this, but it doesn't compute binomial well. It prints 11 for n = 4 and k = 2. Can you take a look at this?
#include <iostream>
long fact(int n, int k);
using namespace std;
int main()
{
int number;
cin>>number;
int t[number][2];
for(int i=0; i<number; i++)
{
cin>>t[i][0];
cin>>t[i][1];
if (t[i][0]<t[i][1]) return 0;
}
for(int i=0; i<number; i++)
{
cout<<fact(t[i][0],t[i][1])<<endl;
}
return 0;
}
long fact(int n, int k)
{
if(n==0 || n==k)
return 1;
else if(n>k)
return fact(n-1,k-1)+fact(n-1, k);
else
return 0;
}
source to share
The factorial grows very quickly and even unfamiliar 64-bit integers n!
for n>20
. The wrong way to implement the binomial coefficient is to use this recursive definition:
binom(n, k) = binom(n-1, k-1) + binom(n-1, k)
This ensures that you only get overflow when it's binom(n,k)
too large to fit the size of your integral type.
source to share
On Linux, 32-bit long is the same as int and is suitable for 32-bit. On Linux 64bit long 64bit. On Windows 32-bit and 64-bit length is a 32-bit object
You should use long long
to ensure that 64 bits are used, although this may not be enough to overcome the overflow. Use recursive binomial formula if possible
source to share