Binomial coefficient function C++ incorrect answer n>13

Question

I'm trying to learn C++ and hence I'm trying to do a function to calculate the binomial coefficient. The code works up to a n of 12, for larger values the generated result is incorrect. I'm grateful for your input.

long double binomial(int n, int k) {
int d = n-k;
int i = 1, t = 1, n1 = 1, n2 = 1;
if (d == 0) {
    return 1;
} else if (n==0) {
    return 1;
} else {
    while (i <=n) {
        t *= i;
        if (i == d) {
            n1 = t;
            cout << t;
        }
        if (i == k) {
            n2 = t;
            cout << t;
        }
        i++;
    }
}
return t/n1/n2;
}
int main() {
int n, k;
cout << "Select an integer n: \n";
cin >> n;
cout << "Select an integer k: \n";
cin >> k;

long double v = binomial(n,k);
cout << "The binomial coefficient is: " << v << "\n";
return 0;
}

Answer 1

If int is 32 bits long on your system (very common nowadays), then the factorial of 13 doesn't fit into it (6227020800 > 2147483647).

Either transition to something bigger (unsigned long long, anyone?), or use a bigint library, or come up with a better/more clever algorithm that doesn't involve computing large factorials, at least not directly.

Answer 2

An int variable can only hold numbers up to a certain size. This varies from compiler to compiler and platform to platform but a typical limit would be around 2 billion. Your program is using numbers bigger than that so you get errors.

If you want to compute with big integers the answer is to get a big integer library. GMP is a popular one.

Answer 3

One of the suggests would be to use some other type.

Here is a list of integer types, sizes and limits.

--------------------------------------------------------------------------------------
|type               |size (B)|Limits                                                 |
--------------------------------------------------------------------------------------
|long long          |8       |–9,223,372,036,854,775,808 to 9,223,372,036,854,775,807|
--------------------------------------------------------------------------------------
|unsigned long long |8       |0 to 18,446,744,073,709,551,615                        |
--------------------------------------------------------------------------------------
|int                |4       |–2,147,483,648 to 2,147,483,647                        |
--------------------------------------------------------------------------------------
|unsigned int       |4       |0 to 4,294,967,295                                     |
--------------------------------------------------------------------------------------
|short              |2       |–32,768 to 32,767                                      |
--------------------------------------------------------------------------------------
|unsigned short     |2       |0 to 65,535                                            |
--------------------------------------------------------------------------------------
|char               |1       |–128 to 127                                            |
--------------------------------------------------------------------------------------
|unsigned char      |1       |0 to 255                                               |
--------------------------------------------------------------------------------------

Note long and int usually are the same size.

Note those limits aren't the same on all architectures standart guarantee only two things about variable sizes:

1. 1 = sizeof(char) = sizeof(unsigned char)
2. 2 = sizeof(shor) = sizeof(unsigned short) <= sizeof(int) = sizeof(unsigned int) <= sizeof(long) = sizeof(unsigned long) <= sizeof(long long) = sizeof(unsigned long long)

---

Another option is to use bigint library, however in this case calculations will take more time but will fit.