为什么使用int64_t给出错误的结果,而double工作正如预期的简单整数乘法

Question

这是我的代码:

using integer = int64_t;

integer factorial(integer number) {
    return number <= 0 ? 1 : number * factorial(number - 1);
}

integer binomial_coefficent(integer n, integer r) {
    return factorial(n) / (factorial(r) * factorial(n - r));
}

int main()
{
    using namespace std;
    cout << binomial_coefficent(40, 20) << endl;
    return 0;
}

这打印

0

这是错误的答案,但如果我将整数类型更改为将打印1.37847e+11 哪个是正确答案,我的问题是为什么使用int64_t给我错误的答案

Answer 1

和int64_t也没有溢出

但确实如此.对于这样的调试,您可以在GCC或clang中使用-fsanitize=signed-integer-overflow(暗示-fsanitize=undefined)运行它来查看:

运行时错误:有符号整数溢出:21*2432902008176640000无法在类型'long'
运行时错误中表示:有符号整数溢出:2432902008176640000*2432902008176640000无法以'long'类型表示

Answer 2

40!是关于8e47.64位有符号整数可以保持最大值2^63-1,大约为1e19.

factorial(40) 溢出,并且由于有符号整数类型的溢出是未定义的行为,因此无法解释您观察到的任何内容.

Answer 3

欢迎来到有限精度数字的世界!事实(40)是815915283247897734345611269596115894272000000000或0x8eeae81b84c7f27e080fde64ff05254000000000,这显然不适合即使在uint64_t128位也不是,long long因为它实际上需要160位!

但二项式系数40,20确实可以使用计算机来计算,uint64_t只要你使用人类在计算机到处前所使用的正确算法:

integer binomial_coefficient(integer n, integer r) {
    integer bc = 1;
    integer q = n - r;
    for(integer i=1; i<=r; i++) {
        br = br * (q + i) / i;
    }
    return bc;
}

这个将给你正确的137846528820值,没有溢出.

(上面的函数省略了r <= n/2的测试,可以进行额外的优化,因为Cn,p是构造Cn,np)