Best way to avoid number polarity reversal if multiplying two big numbers in Java

Question

My question is related to this How can I check if multiplying two numbers in Java will cause an overflow?

In my application, x and y are calculated on the fly and somewhere in my formula I have to multiply x and y.

     int x=64371;
     int y=64635;

     System.out.println((x*y));

I get wrong output as -134347711

I can quickly fix above by the changing variable x and y from type int to long and get correct answer for above case. But, there is no gurantee that x and y won't grow beyond max capacity of long as well.

Question

1. Why does I get a negative number here, even though I am not storing the final result in any variable? (for curiosity sake)

2. Since, I won't know the value of x and y in advance, is there any quicker way to avoid this overflow. Maybe by dividing all x and y by a certain large constant for entire run of the application or should I take log of x and y before multiplying them? (actual question)

EDIT:

Clarification

The application runs on a big data set, which takes hours to complete. It would be nicer to have a solution which is not too slow.

Since the final result is used for comparison (they just need to be somewhat proportional to the original result) and it is acceptable to have +-5% error in the final value if that gives huge performance gain.

Answer 1

If you know that the numbers are likely to be large, use BigInteger instead. This is guaranteed not to overflow, and then you can either check whether the result is too large to fit into an int or long, or you can just use the BigInteger value directly.

BigInteger is an arbitrary-precision class, so it's going to be slower than using a direct primitive value (which can probably be stored in a processor register), so figure out whether you're realistically going to be overflowing a long (an int times an int will always fit in a long), and choose BigInteger if your domain really requires it.

Answer 2

1. You get a negative number because of an integer overflow: using two-s complement representation, Java interprets any integer with the most significant bit set to 1 as a negative.
2. There are very clever methods involving bit manipulation for detecting situations when an addition or subtraction would result in an overflow or an underflow. If you do not know how big your results are going to be, it is best to switch to BigInteger. Your code would look very different, though, because Java lacks operator overloading facilities that would make mathematical operations on BigInteger objects look familiar. The code will be somewhat slower, too. However, you will be guaranteed against overflows and underflows.

EDIT :

it is acceptable to have +-5% error in the final value if that gives huge performance gain.

+-5% error is a huge allowance for error! If this is indeed acceptable in your system, than using double or even float could work. These types are imprecise, but their range is enormously larger than that of an int, and they do not overflow so easily. You have to be extremely careful, though, because floating-point data types are inherently inexact. You need to always keep in mind the way the data is represented to avoid common precision problems.

Answer 3

Why does I get a negative number here, even though I am not storing the final result in any variable? (for curiosity sake)

x and y are int types. When you multiply them, they are put into a piece of memory temporarily. The type of that is determined by the types of the originals. int*int will always yield an int. Even if it overflows. if you cast one of them to a long, then it will create a long for the multiplication, and you will not get an overflow.

Since, I won't know the value of x and y, is there any quicker way to avoid this overflow. Maybe by dividing all x and y by a certain large constant for entire run of the application or should I take log of x and y before multiplying them? (actual question)

If x and y are positive then you can check

if(x*y<0)
{
    //overflow
}
else
{
    //do something with x*y
}

Unfortunately this is not fool-proof. You may overrun right into positive numbers again. for example: System.out.println(Integer.MAX_VALUE * 3); will output: 2147483645.

However, this technique will always work for adding 2 integers.

As others have said, BigInteger is sure not to overflow.

Answer 4

Negative value is just (64371 * 64635) - 2^32. Java not performs widening primitive conversion at run time.

Answer 5

Multiplication of ints always result in an int, even if it's not stored in a variable. Your product is 4160619585, which requires unsigned 32-bit (which Java does not have), or a larger word size (or BigInteger, as someone seem to have mentioned already).

You could add logs instead, but the moment you try to exp the result, you would get a number that won't round correctly into a signed 32-bit.

Answer 6

Since both multiplicands are int, doing the multiplication using long via casting would avoid an overflow in your specific case:

System.out.println(x * (long) y);

You don't want to use logarithms because transcendental functions are slow and floating point arithmetic is imprecise - the result is likely to not be equal to the correct integer answer.