ここに私のコードがあります:
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を使用すると間違った答えが出る理由です
回答 3 件
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のテストを省略します)
でもそうです。このようなものをデバッグするには、
-fsanitize=signed-integer-overflow
でこれを実行できます。 (-fsanitize=undefined
によって暗示される )GCCまたはclangで次を確認します。