Any problems doing a multiplication with potential overflow and then verifying with division?

Question

Suppose I have two size_t variables and I need to multiply them and get result as size_t.

size_t first = ...;
size_t second = ...;
size_t result = first * second;

They might overflow so I need to check for that.

The "clean" way would be to first check that multiplication is possible using division:

if( second != 0 && first > ((size_t)-1) / second ) {
   //handle overflow
}
//proceed with computing first * second

The seemingly less "clean" way is to first multiply and then check the result with division:

size_t result = first * second;
if( second != 0 && result / second != first )
   //handle overflow
}

However because unsigned numbers multiplication "safely overflows" by wrapping around zero this works just fine and looks like equivalent to the former code (which first checks, then multiplies).

Are there any potential problems with the second code? Will it always be as good as the first one?

Answer 1

I would say that not only do you need to check the division, but you should also check the remainder too:

if( second != 0 && (result / second != first || (result % second) != 0))

If c=b*a, then there's only one value of c such as c/b=a. Trying to divide any other value by b will not produce a.

However that's not integer math, but real math. Since integer division rounds off, the formula won't technically be true, since, provided that b is at least 2, (c+1)/b would also be a, for some values of c.

Answer 2

From a mathematical POV, if

((a*b) mod (2^n)) / b == a  

is true for some overflowing values (this implies a and b both not 0), then it´s a problem.
Accoring to Wolfram Alpha, it´s never true for overflows because to get a result, the bitlength
of the result variable n has to be bigger the the required bitlength of a*b (log[2](a*b)).

Code-wise, I can´t think of any problem just now either.

Answer 3

The first method you point above is definitelly incorrect. Casting a negative number to an unsigned type is incorrect as used above and deals to Undefined Behaviour.

The second method, as the only way a product can be different from the multiplication of two factors is having an overflow in the middle, would be correct, but again, overflow can deal to Undefined behaviour and as such, would be incorrect (You are implicitly thinking that the overflow will result from a multiplication modulo operation, and the result indeed is undefined).

One way to check for possible overflow could be:

if (MAX_UINT / one_of_the_factors < the_other_factor) ...

This is completely defined and allow you to detect the overflow before doing the actual multiplication in a portable way.