次のような式を計算する必要があります: A*B - C*D、型は次のとおりです:signed long long int A, B, C, D;各数値は非常に大きくなる可能性があります (その型をオーバーフローしない)。 はA*Bオーバーフローを引き起こす可能性がありますが、同時に式はA*B - C*D非常に小さくなる可能性があります。 正しく計算するにはどうすればよいですか?
たとえばMAX * MAX - (MAX - 1) * (MAX + 1) == 1、MAX = LLONG_MAX - n、n は自然数です。
ベストアンサー1
これはあまりにも些細なことのように思えます。しかし、A*Bオーバーフローする可能性があります。
精度を落とさずに次の操作を実行できます
A*B - C*D = A(D+E) - (A+F)D
= AD + AE - AD - DF
= AE - DF
^smaller quantities E & F
E = B - D (hence, far smaller than B)
F = C - A (hence, far smaller than C)
この分解はさらに
@Gian が指摘したように、型が unsigned long long の場合、減算演算中に注意が必要になる場合があります。
例えば、質問の場合、1回の反復で済みます。
MAX * MAX - (MAX - 1) * (MAX + 1)
A B C D
E = B - D = -1
F = C - A = -1
AE - DF = {MAX * -1} - {(MAX + 1) * -1} = -MAX + MAX + 1 = 1