为什么使用 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;
}

这会打印

这是错误的答案，但如果我将整数类型更改为双精度，则会打印 1.37847e+11 这是正确的答案，我的问题是为什么使用 int64_t 给我错误的答案

Answer 1

and int64_t doesn't overflow either

虽然如此。对于像这样的调试，你可以在 GCC 或 clang 中使用 -fsanitize=signed-integer-overflow（由 -fsanitize=undefined 暗示）运行来查看：

runtime error: signed integer overflow: 21 * 2432902008176640000 cannot be represented in type 'long'
runtime error: signed integer overflow: 2432902008176640000 * 2432902008176640000 cannot be represented in type 'long'

Answer 2

40! 大约是 8e47。一个 64 位有符号整数最多可以容纳 2^63-1，大约 1e19.

factorial(40) 确实会溢出，并且由于有符号整数类型的溢出是未定义的行为，所以您观察到的任何事情都无法解释。

Answer 3

欢迎来到有限精度数字的世界！ fact(40) 是 815915283247897734345611269596115894272000000000 或 0x8eeae81b84c7f27e080fde64ff05254000000000 显然不适合 uint64_t 既不适合 128 位 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,n-p）

为什么使用 int64_t 给出错误的结果，而 double 对于简单整数乘法按预期工作

why using int64_t gives wrong result while double works as expected for simple integer multiplications

c++

double

int

factorial