Биномиальный коэффициент

Question

У меня есть код, который вычисляет биномиальный коэффициент, но когда число больше 20, оно начинает вычисляться неправильно, в чем проблема? Спасибо

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

например 12 и 5 = 792, что правильно, но 20 и 4 = -2, что не правильно

Answer 1

Ваш bin Функция вычисляет факториал. Факториал 21 не вписывается в long,

Вы уже полагаетесь на детали реализации. long требуется только 32 бита, но в вашей системе это 64. Если бы это было только 32, то вы потерпели бы неудачу гораздо раньше.

Answer 2

20! = 2432902008176640000, что намного выше long int может держать (обычно 2147483647). использование double вместо.

Answer 3

Вы вычисляете факториал n, используя

bin(n);

Вы бежите за предел long, когда n>=20.

Как указывалось в комментариях @SteveJessop, вы превысили лимит, даже если бы использовали unsigned long long (самый длинный тип с фиксированной точкой), который имеет диапазон от 0 to 18446744073709551615

Вы можете использовать int-массив для хранения вашего результата, как описано здесь.