3

In one of the books that I am reading, following function is used to determine 2's complement integer multiplication overflow.

int tmult_ok(int x, int y) {
int p = x*y;
return !x || p/x == y;
}

While this works, how do I prove its correctness in all the cases? How do I ensure that p != x*y when there is an overflow?

Here is what I understand:

  1. When you multiply 2 integers of size "w- bits", the result can be 2w bits.
  2. The computation truncates higher order w bits. So we are left with lower order w bits. 3.Let us say that P = lowest w-bits
  3. Then, we need to prove that (P/x != y) and (P/y !=x) when there is overflow.
  4. My confusion lies here. How can you say that (P/x !=y) when there is no overflow? Isn't it possible that the bit pattern of P when divided by x could yield y even when there is an overflow?
Improve this question
3

3 Answers 3

Reset to default
4

tmult_ok(x, y) fails anytime x*y in int p = x*y; overflows as that is undefined behavior (UB).
It also fails a corner case like tmult_ok(INT_MIN, -1) for the same reason.
It does not portably "work".

An alternative (and others for /,-,+) which does not depend on 2's complement. Notice this returns the opposite of tmult_ok().

int is_undefined_mult1(int a, int b) {
  if (a > 0) {
    if (b > 0) {
      return a > INT_MAX / b;       // a positive, b positive
    }
    return b < INT_MIN / a;         // a positive, b not positive
  }
  if (b > 0) {
    return a < INT_MIN / b;         // a not positive, b positive
  }
  return a != 0 && b < INT_MAX / a; // a not positive, b not positive
}

How do I ensure that p != x*y when there is an overflow?

Portable code cannot. With signed integer math in C, overflow is UB. Code should detect a potential overflow without first performing the multiplication. @Quentin @Eugene Sh.

how do I prove its correctness in all the cases?

Form a reference test with uses 2x wide math. If int is 32-bit, compare tmult_ok() to a multiplication using 64-bit math and see if the product in in range. @rici

int tmult_ok_ll(int x, int y) {
  long long prod = x;
  prod *= y;
  return (prod >= INT_MIN && prod <= INT_MAX);
}

Trying all combinations is a brute force approach - likely too long for 32-bit int.

Try a subset of all combinations, for each x,y,try INT_MIN, INT_MIN-1, INT_MIN-2, -2,-1, 0, 1, 2, , INT_MAX-1, INT_MAX. (10*10 tests)

Also a subset of all combinations, for each values +/- within 2 of sqrt(INT_MAX). (10*10 tests)

Also a few million random values in the int range would be prudent.

This may not be sufficient, yet if code passes this, there are very few corner cases left - which are very dependent on your source code.

See also @Eric Postpischil

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

You could test exhaustively with 16-bit integers, and that would be a reasonable exercise of the algorithm for 32-bit integers. But I expect an algorithm this simple is susceptible to formal proof.
0

overflow like underflow are undefined behavior meaning that the compiler can consider they never happen and simplify code that depend on it.so you can't detect if an overflow has already occurred

instead should check if an operation that might overflow is going to overflow 

int tmult_ok(int x, int y) {
  if (MAX_INT / y >= x)
    //throw somthing
  return x*y;
}
Improve this answer

1 Comment

Good only for the same sign x and y. Also should be >= (yet some corner cases should be examined...).
0

You can check the overflow flag (https://en.wikipedia.org/wiki/Overflow_flag)

In computer processors, the overflow flag (sometime called V flag) is usually a single bit in a system status register used to indicate when an arithmetic overflow has occurred in an operation, indicating that the signed two's-complement result would not fit in the number of bits used for the operation (the ALU width).

Example of how to access it: https://www.linuxquestions.org/questions/programming-9/c-how-to-check-the-overflow-flag-930420/#post4612830

Improve this answer

3 Comments

Even if the program is executing on a system with such a flag, there is no guarantee the compiler performed the multiplication with an instruction that would have set the overflow flag. And there are other problems with this idea, such as ensuring the read of the overflow flag immediately follows the multiplication instruction (since the compiler may reorder things).
To expand on this, @yoones should realize that the example he linked used assembly to add the numbers as well. If you start mixing compiled code and assembled, you never know if you're getting what you think you are without rigorous testing, and even then a newer compiler may decide differently, wrecking your old solution.
The solution to that is to use compiler-specific functions, such as GCC's overflow-checking intrinsics.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.