int64_tを使用すると間違った結果が得られるのに、doubleは単純な整数乗算で期待どおりに動作する

bugfix> c++ > 投稿

ここに私のコードがあります：

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

間違った答えですが、整数型をdoubleに変更すると 1.37847e+11 が出力されますこれは正しい答えです、私の質問は、int64_tを使用すると間違った答えが出る理由です

c++

int

double

回答 3 件

  • and int64_t doesn't overflow either

    でもそうです。このようなものをデバッグするには、 -fsanitize=signed-integer-overflow でこれを実行できます。  （ -fsanitize=undefined によって暗示される ）GCCまたはclangで次を確認します。

    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'

  • 40!   8e47 について 。 64ビットの符号付き整数は、最大 2^63-1 で保持できます。 、 1e19 について 。

    factorial(40)  オーバーフローは発生しますが、符号付き整数型のオーバーフローは未定義の動作であるため、観察することは説明できません。

  • 有限精度数の世界にようこそ！ 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の正しい値が得られます。

    （上記の関数は、Cn、pが構造上のCn、n-pであるため、追加の最適化が可能なr<= n/2のテストを省略します）

あなたの答え

関連記事