How to avoid overflow in expr. A * B - C * D

c++ c integer-overflow
NGix picture NGix · Nov 5, 2012 · Viewed 8k times · Source

I need to compute an expression which looks like: A*B - C*D, where their types are: signed long long int A, B, C, D; Each number can be really big (not overflowing its type). While A*B could cause overflow, at same time expression A*B - C*D can be really small. How can I compute it correctly?

For example: MAX * MAX - (MAX - 1) * (MAX + 1) == 1, where MAX = LLONG_MAX - n and n - some natural number.

Answer

Anirudh Ramanathan picture Anirudh Ramanathan · Nov 5, 2012

This seems too trivial I guess. But A*B is the one that could overflow.

You could do the following, without losing precision

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)

This decomposition can be done further.
As @Gian pointed out, care might need to be taken during the subtraction operation if the type is unsigned long long.

For example, with the case you have in the question, it takes just one iteration,

 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

Related questions

How do I detect unsigned integer multiply overflow?

I was writing a program in C++ to find all solutions of ab = c, where a, b and c together use all the digits 0-9 exactly once. The program looped over values of a and b, and it ran a …

Read More
Why is unsigned integer overflow defined behavior but signed integer overflow isn't?

Unsigned integer overflow is well defined by both the C and C++ standards. For example, the C99 standard (§6.2.5/9) states A computation involving unsigned operands can never overflow, because a result that cannot be represented by the resulting unsigned integer …

Read More
Detecting signed overflow in C/C++

At first glance, this question may seem like a duplicate of How to detect integer overflow?, however it is actually significantly different. I've found that while detecting an unsigned integer overflow is pretty trivial, detecting a signed overflow in C/…

Read More