Переполнение при вычислении комбинаций

Question

Я пытаюсь вычислить комбинацию C (40, 20) в C++, однако типы данных в C++, похоже, не могут правильно обрабатывать этот расчет, даже если я использовал тип данных long long. Ниже приведен мой код:

#include <iostream> 

long long fac(int x) { 
    register long long i,f = 1; // Optimize with regFunction 
    for(i = 1;i <= x;i++) 
     f *= i; 
    std::cout << f << std::endl; 
    return f; 
} 

// C(n,r) = n!/r!(n-r)! 
long long C(long long n, long long r) { 
    return fac(n)/(fac(r) * fac(n - r)); 
} 

int main(int argc, char const *argv[]) { 
    std::cout << C(40, 20) << std::endl; 
    return 0; 
} 

Любая идея для решения этой проблемы?

Answer 1

Compute C сразу, немедленно выполняя деление после умножения:

long long C(long long n, long long r) 
{ 
    long long f = 1; // Optimize with regFunction 
    for(auto i = 0; i < r;i++) 
     f = (f * (n - i))/(i + 1); 
    return f ; 
} 

Результат должен быть точным (деление без остатков, до перелива), так как любое целое число раз, присутствующего в (я + 1) уже присутствует в (n -i).(Не должно быть слишком сложно доказать)

Answer 2

Даже если вы использовали uint64 aka ulonglong, максимальное значение равно 18446744073709551615, тогда как 40! 815915283247897734345611269596115894272000000000, который является немного больше.

Я рекомендую вам использовать GMP для такого рода математики

Answer 3

Проблемы в том, что факториалы получить большие очень быстро. 40! слишком велика для хранения в long long. К счастью, вам действительно не нужно вычислять этот номер здесь, так как вы можете уменьшить долю в вычислении C(n, r) перед ее вычислением. Это дает уравнение (от Wikipedia):

Это работает намного лучше, так как K! ( r! В вашем коде) намного меньше, чем n!. Однако в какой-то момент он также сломается.

В качестве альтернативы вы также можете использовать определение повторения путем реализации рекурсивного алгоритма. Однако это будет очень неэффективно (экспоненциальное время работы), если вы не мнимаете промежуточные результаты.

Answer 4

Ленивый выход - использовать библиотеку, которая поддерживает множественную точность, например GNU GMP.

После того, как вы правильно установили его (имеется в репозиториях на большинстве дистрибутивов Linux), сводится к тому:

• добавления #include <gmpxx.h> в исходный файл
• заменяющего long long с mpz_class
• компиляции с -lgmpxx -lgmp

Источник:

#include <iostream> 
#include <gmpxx.h> 

mpz_class fac(mpz_class x) { 
    int i; 
    mpz_class f(1); // Optimize with regFunction 
    for(i = 1;i <= x;i++) 
     f *= i; 
    std::cout << f << std::endl; 
    return f; 
} 

// C(n,r) = n!/r!(n-r)! 
mpz_class C(mpz_class n, mpz_class r) { 
    return fac(n)/(fac(r) * fac(n - r)); 
} 

int main(int argc, char const *argv[]) { 
    std::cout << C(40, 20) << std::endl; 
    return 0; 
} 

Компиляция и запуск:

$ g++ comb.cpp -lgmpxx -lgmp -o comb 
$ ./comb 
2432902008176640000 
2432902008176640000 
815915283247897734345611269596115894272000000000 
137846528820 

Если вы хотите быть уверенными, Вы можете сделать гораздо больше, но это поможет вам ответы.

Answer 5

Ваши цифры растут слишком много, и это общая проблема в таких расчетах, и я боюсь, что нет простого решения. Даже если вы могли бы уменьшить чуток количество умножений вы будете делать, вероятно, до сих пор вы будете в конечном итоге к переполнению с long long

Вы могли бы хотеть проверить эти:

https://mattmccutchen.net/bigint/

https://gmplib.org/

Я знаю, что существуют различные алгоритмические подходы к этому вопросу. Я помню, что были некоторые решения использовать строки для хранения целочисленных представлений и прочее, но, как сказал @Konrad, это может быть плохой подход к делу.