How to detect an arithmetic overflow

[prilmeie]

Hi all,

I've had serious arithmetic overflow problems with the Problem 106. Therefore I have written some overlow checking code (in C++) for myself, but I am just curious if you know some slightly faster one, as this is obviously O(1):

[cpp]
/**
* Performs an addition of parameters a and b. If an arithmetic
* overflow happens, then overflow_value will be returned.
*/
inline int detect_addition_overflow( const int a, const int b, const int overflow_value )
{
int result = a + b;

if ( result - a != b || result - b != a ) {
return overflow_value;
} else {
return result;
}
}

/**
* Performs a multiplication of parameters a and b. If an arithmetic
* overflow happens, then overflow_value will be returned.
*/
inline int detect_multiplication_overflow( const int a, const int b, const int overflow_value )
{
int result = a * b;

if ( a != 0 && result / a != b ) {
return overflow_value;
} else if ( b != 0 && result / b != a ) {
return overflow_value;
} else {
return result;
}
}[/cpp]

[ericschmidt]

Hi prilmeie,

That detect_addition_overflow algorithm won't work. The machine has an adder with int-width and wraps around when overflowing. Checking the expression "result - a" will wrap around right back again. Try out:
detect_addition_overflow (0x80000000,0x80000000,ov_val) ... it will return 0x0 and not ov_val which is obviosly wrong.
Since this is all signed arithmetic, your checks in detect_addition_overflow would have to check correctness of the signs - like:

if ((sign(a) == sign(b)) && (sign(result) != sign(a))) return ov_val;

but that would not be the whole function yet. By the way which value did you want to use for ov_val? If you want to detect the overflow by asking for that value, you are forbidding this value as normal calculated result. You're not going to be happy with that.

Yours, Eric

[prilmeie]

Yes, you are right, I am indeed missing a sign check. For the value of ov_value, one could expect perhaps -1, for an addition of two positive integers, or +1 for an addition of two negative integers, whose values cannot be the result of the operation if everything went Ok. Otherwise an overflow cannot occur.

For the multiplication method I would suggest the value 0. So this leads to a much more complicated and time intensive value check:

[cpp]
/**
* Performs an addition of parameters a and b. If an arithmetic
* overflow happens, then overflow_value will be returned.
*/
inline int detect_addition_overflow( const int a, const int b, const int overflow_value )
{
int result = a + b;

if ( a > 0 && b > 0 && result <= 0 ) {
return overflow_value;
} else if ( a < 0 && b < 0 && result >= 0 ) {
return overflow_value;
} else if ( result - a != b || result - b != a ) {
return overflow_value;
} else {
return result;
}
}

/**
* Performs a multiplication of parameters a and b. If an arithmetic
* overflow happens, then overflow_value will be returned.
*/
inline int detect_multiplication_overflow( const int a, const int b, const int overflow_value = 0 )
{
int result = a * b;

if ( a > 0 && b > 0 && result <= 0 ) {
return overflow_value;
} else if ( a < 0 && b < 0 && result >= 0 ) {
return overflow_value;
} else if ( a != 0 && result / a != b ) {
return overflow_value;
} else if ( b != 0 && result / b != a ) {
return overflow_value;
} else {
return result;
}
}[/cpp]

[Jordan Gordeev]

The right way to write detect_addition_overflow() is the following (see Leendert Ammeraal, Algorithms and Data Structures in C++, John Wiley & Sons, ISBN 0-471-96355-0):

[cpp]inline int detect_addition_overflow(int a, int b, int overflow_value) {
int result = a + b;
if (result >= a) return result;
else return overflow_value;
}[/cpp]

[ericschmidt]

Hi all,

The 2nd code from prilmeie looks functional now, although it still carries some "unnecessary code":
e.g. the expression ( result - a != b || result - b != a ) is never true since + and - are performed in a "circular" manner. You can simply try that out on any debugger. The code from Jordan is not functional - I'm sure - try out my first test pair (a = b = 0x80000000) - it will return 0x0 and not ov_val.

I've added a proposal for the two functions. I would also prefer a nested if structure in detect_multiplication_overflow to be absolutely sure that the compiler does not try to evaluate the division after finding a = 0. Also, one division is enough.

I would propose:

inline int detect_addition_overflow( const int a, const int b, const int overflow_value )
{
int result = a + b;

if ((a>0 && b>0 && result<=0) || (a<0 && b<0 && result>=0)) {
return overflow_value;
} else {
return result;
}
}

inline int detect_multiplication_overflow( const int a, const int b, const int overflow_value = 0 )
{
int result = a * b;

if ( a != 0 ) {
if ( result/a != b ) {
return overflow_value;
} else {
return result;
}
} else {
return result;
}
}

Note: You cannot use detect_addition_overflow for subtractions by using detect_addition_overflow(a, -b, ov_val) since the unary "-" operator overflows for one special value (b = 0x80000000) whose positive counterpart cannot be represented within the range of the positive numbers. This would already happen when passing the parameters and cannot be detected within detect_addition_overflow. A separate detect_subtraction_overflow function would be necessary.

Yours, Eric

[prilmeie]

I do not agree with you that the check for the inversion value in detect_addition_overflow is never true. Let me prove this by a small example:

Asume that we are using a 32bit machine, i.e. int has the length 32 bit. Let a = 2147483647, that is INT_MAX, and b = 2. There undoubtly will be an overflow which leads to the value: -2147483645 (If I haven't made a misstake, I have computed the values by hand). Subtracting b from the result leads to -2147483647 which is not equal to a. Maybe the check is superfluous, but it indicates an overflow. This comes from the fact that the maximum absolute value an integer can store is 0xFF... which does not have a positive correspondent value.

You can also slightly improve the performance of the detect_multiplication_overflow method by using:

[cpp]inline int detect_multiplication_overflow( const int a, const int b, const int overflow_value = 0 )
{
if ( a != 0 ) {
int result = a * b;

if ( result / a != b ) {
return overflow_value;
} else {
return result;
}
} else {
return 0;
}
}[/cpp]

[prilmeie]

Yes you are right, I have made a calculation mistake which lead me to the wrong corollary, that the inverse operation could detect any overflow error. If you think twice (and analytically) you can easily detect, that this is not the case: An addition in a computer must allways be seen as a circlic operation. The best way to illustrate this is on some kind of clock image. So I must excuse my contradicting opinion to ericschmidt, which afterwards was proven as wrong. I will also summarize the results of this thread at the end of the post. As ericschmidt allready stated, the detect_addition_overflow is not suitable for subtraction, if one of the parameters equals INT_MIN, which cannot be checked inside the function.

I would like to thank all of you who have shared their knowledge with me in this thread. I have enjoyed it very much.

Regards,
Franz

[cpp]
inline int detect_addition_overflow( const int a, const int b, const int overflow_value )
{
int result = a + b;

if ( (a>0 && b>0 && result<=0) || (a<0 && b<0 && result>=0) ) {
return overflow_value;
} else {
return result;
}
}

inline int detect_multiplication_overflow( const int a, const int b, const int overflow_value = 0 )
{
if ( a != 0 ) {
int result = a * b;

if ( result / a != b ) {
return overflow_value;
} else {
return result;
}
} else {
return 0;
}
}
[/cpp]