Overflow and range checking for arithmetic operations

Question

How can we check whether an arithmetic operation will exceed the upper bounds of the data type before actually applying it.

Say upperbound for short in java is 32767 and I am multiplying 328*100, I can't actually do comparison with Short.MAX_VALUE because after multiplication answer would already be overflown and answer would be -32736 which is certainly smaller than Short.MAX_VALUE

Take another example say I am int value of computing 17^10 (17 to the power 10) in a for loop. How do I know at what stage my answer got overflowed.

This Short and int thing is just an example. Think of this problem in bigger perceptive what exactly can be done for all data types.

I tried googling but found no good link which helps understand the concept.

Answer 1

There are 3 possible methods for overflow checking:

Use a larger type and downcast: Cast the inputs to the next larger primitive integer type and perform the arithmetic in the larger size. Check each intermediate result for overflow of the original smaller type; throw an ArithmeticException if the range check fails.

Pre-check inputs: Check the inputs to each arithmetic operator to ensure that overflow cannot occur. Again throw an ArithmeticException when the operation would overflow if it was performed, otherwise perform the operation.

E.g.:

static void preAddCheck(int left, int right) throws ArithmeticException {
   if (right > 0 ? left > Integer.MAX_VALUE - right : left < Integer.MIN_VALUE - right) {
    throw new ArithmeticException("Integer overflow");
  }
}

BigInteger: Convert the inputs into objects of type BigInteger and perform all arithmetic using BigInteger methods. ArithmeticException thrown on overflow.

Answer 2

There is a plan to include such methods in the Math package in Java 8, but I don't know what the current status is. Some source code is available here. I don't how tested the implementation is, but that could give you ideas.

For example, int multiplication is done by using longs:

public static int multiplyExact(int x, int y) {
    long r = (long)x * (long)y;
    if ((int)r != r) {
        throw new ArithmeticException("long overflow");
    }
    return (int)r;
}

But long multiplication uses a more complex algorithm:

public static long multiplyExact(long x, long y) {
    long r = x * y;
    long ax = Math.abs(x);
    long ay = Math.abs(y);
    if (((ax | ay) >>> 31 != 0)) {
        // Some bits greater than 2^31 that might cause overflow
        // Check the result using the divide operator
        // and check for the special case of Long.MIN_VALUE * -1
       if (((y != 0) && (r / y != x)) ||
            (x == Long.MIN_VALUE && y == -1)) {
            throw new ArithmeticException("long overflow");
        }
    }
    return r;
}  

Answer 3

I'd do the calculation using the largest possible type, BigInteger/BigDecimal. I'd then assign the value to the appropriate type depending upon its magnitude... Interestingly there are some useful methods for this... shortValueExtract will throw an ArithmetricException if the value cannot be contained in a short..

BigDecimal result = BigDecimal.valueOf(328).multiply(
        BigDecimal.valueOf(100));
try {
    short shortResult = result.shortValueExact();
} catch (ArithmeticException e) {
    // overflow
    System.out.println("Overflow!");
}

try {
    int intResult = result.intValueExact();
} catch (ArithmeticException e) {
    // overflow
}