a、b、c を大きくない正の整数とします。a/b/c は常に a/(b * c) と C# の整数演算で等しくなりますか? 私の場合、C# では次のようになります。
int a = 5126, b = 76, c = 14;
int x1 = a / b / c;
int x2 = a / (b * c);
だから私の質問は：x1 == x2すべてのa、b、cに対してですか？
質問する
4041 次
6 に答える
77
私はこの質問がとても気に入ったので、2013 年 6 月 4 日にブログの題材にしました。素晴らしい質問をありがとう！
大きめのケースが手に入りやすいです。例えば：
a = 1073741823;
b = 134217727;
c = 134217727;
b * c負の数にオーバーフローするためです。
私はそれに加えて、チェックされた算術演算では、 との違いが、動作するプログラムとクラッシュするプログラムの違いになる可能性があるa / (b * c)という事実を追加します。(a / b) / cと の積が整数の境界をオーバーフローする場合、前者はチェックされたコンテキストでクラッシュしますb。c
小さい正の整数、たとえば short に収まるほど小さい正の整数の場合、同一性を維持する必要があります。
Timothy Shields が証明を投稿しました。ここで別の証明を提示します。ここでの数値はすべて非負の整数であり、オーバーフローする演算はないと仮定します。
の整数除算は、 、どこでのようなx / y値を見つけます。qq * y + r == x0 <= r < y
したがって、除算は次のようなa / (b * c)値を見つけます。q1
q1 * b * c + r1 == a
どこ0 <= r1 < b * c
除算は最初に次のような( a / b ) / c値を見つけます。qt
qt * b + r3 == a
そして、次のq2ような値を見つけます
q2 * c + r2 == qt
これを for に置き換えると、次のqtようになります。
q2 * b * c + b * r2 + r3 == a
どこ0 <= r2 < cと0 <= r3 < b。
同じに等しい 2 つのものは互いに等しいので、次のようになります。
q1 * b * c + r1 == q2 * b * c + b * r2 + r3
q1 == q2 + xいくつかの整数を想定しxます。に代入して を解きxます:
q2 * b * c + x * b * c + r1 = q2 * b * c + b * r2 + r3
x = (b * r2 + r3 - r1) / (b * c)
どこ
0 <= r1 < b * c
0 <= r2 < c
0 <= r3 < b
x0 より大きくなる可能性はありますか? いいえ、次の不等式があります。
b * r2 + r3 - r1 <= b * r2 + r3 <= b * (c - 1) + r3 < b * (c - 1) + b == b * c
したがって、その分数の分子は常に よりも小さいためb * c、xゼロより大きくすることはできません。
xゼロ未満になることはありますか? いいえ、同様の議論により、読者に任せます。
したがって、整数xはゼロであり、したがってq1 == q2.
于 2013-05-30T13:49:17.273 に答える
71
let\は整数除算 ( /2 つの の間の C# 演算子int) を表し、 let/は通常の数学除算を表します。次に、x,y,zが正の整数で、overflow を無視している場合、
(x \ y) \ z
= floor(floor(x / y) / z) [1]
= floor((x / y) / z) [2]
= floor(x / (y * z))
= x \ (y * z)
どこ
a \ b = floor(a / b)
[1]上記の行から行へのジャンプ[2]は、次のように説明されます。範囲内に2 つの整数aとbと 1 つの小数があるとします。それを見るのは簡単ですf[0, 1)
floor(a / b) = floor((a + f) / b) [3]
行内で 、、および[1]を識別する場合、とが等しいことを意味します。a = floor(x / y)f = (x / y) - floor(x / y)b = z[3][1][2]
この証明を負の整数に一般化することはできますが (まだoverflow は無視します)、要点を単純にするために、それは読者に任せます。
オーバーフローの問題について- 適切な説明については、Eric Lippert の回答を参照してください! 彼はまた、ブログの投稿と回答でより厳格なアプローチを採用しています。
于 2013-05-30T14:17:51.507 に答える
4
bとの絶対値が約(約 46 300)c未満で、オーバーフローしない場合、値は常に一致します。オーバーフローした場合、コンテキストでエラーがスローされるか、コンテキストで正しくない値が取得される可能性があります。sqrt(2^31)b * cb * ccheckedunchecked
于 2013-05-30T14:06:48.093 に答える
2
他の人が気づいたオーバーフロー エラーを回避し、常に一致します。
と仮定しましょうa/b=q1、つまりa=b*q1+r1、どこ0<=r1<b. ここで、 、つまり、
と仮定します。
これは、.
のためには、 が必要です。
ただし、必要に応じて、2 つの操作が一致します。a/b/c=q2q1=c*q2+r20<=r2<ca=b(c*q2+r2)+r1=b*c*q2+br2+r1a/(b*c)=a/b/c=q20<=b*r2+r1<b*cb*r2+r1<b*r2+b=b*(r2+1)<=b*c
bまたはが負の場合、これは機能しませんcが、その場合に整数除算がどのように機能するかはわかりません。
于 2013-05-30T14:34:05.280 に答える
0
カウンター例：INT_MIN / -1 / 2
于 2013-06-03T04:51:01.153 に答える
0
楽しみのために私自身の証明を提供します。これもオーバーフローを無視し、残念ながらポジティブのみを処理しますが、証明はきれいで明確だと思います。
目標はそれを示すことです
floor(floor(x/y)/z) = floor(x/y/z)
ここで/は正規除算です (この証明を通して)。
の商と剰余をa/b 一意に として表します (これは、が一意であり、 にも注意a = kb + rすることを意味します)。次に、次のようになります。k,r|r| < |b|
(1) floor(x/y) = k => x = ky + r
(2) floor(floor(x/y)/r) = k1 => floor(x/y) = k1*z + r1
(3) floor(x/y/z) = k2 => x/y = k2*z + r2
したがって、私たちの目標はそれを示すことk1 == k2です。さて、私たちは持っています：
k1*z + r1 = floor(x/y) = k = (x-r)/y (from lines 1 and 2)
=> x/y - r/y = k1*z + r1 => x/y = k1*z + r1 + r/y
したがって：
(4) x/y = k1*z + r1 + r/y (from above)
x/y = k2*z + r2 (from line 3)
ここで、(2) がr1整数 (k1*zは定義により整数) であり、r1 < z(定義により) であることに注目してください。さらに (1) から、 ということがわかりr < y => r/y < 1ます。r1 + r/y次に、(4)の合計を考えます。主張は でr1 + r/y < zあり、これは前の主張から明らかです (なぜなら0 <= r1 < zとr1は整数なので0 <= r1 <= z-1. したがってとなります0 <= r1 + r/y < z)。したがってr1 + r/y = r2、定義によりr2(そうでなければ、剰余の定義と矛盾する2 つの剰余が存在することになります)。x/yしたがって、次のようになります。
x/y = k1*z + r2
x/y = k2*z + r2
という望ましい結論が得られk1 = k2ます。
上記の証明は、追加のケースをチェックする必要があるいくつかの手順を除いて、ネガで機能するはずです...しかし、私はチェックしませんでした。
于 2013-05-31T07:49:32.343 に答える