[解決済み] exprのオーバーフローを回避する方法 A * B - C * D

質問

次のような式を計算する必要があります。 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はある自然数である。

解き方は？

これはあまりに些細なことだと思うのですが。 しかし 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