Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Overflow occurs with multiplication

long m = 24 * 60 * 60 * 1000 * 1000;

The above code creates overflow and doesn't print the correct result.

long m2 = 24L * 60 * 60 * 1000 * 1000;
long m3 = 24 * 60 * 60 * 1000 * 1000L;

The above 2 lines print the correct result.

My questions are-

  1. Does it matter to the compiler which I use, m2 or m3?
  2. How does java starts multiplying? Left to right or right to left? Does 24*60 gets computed first or 1000*1000?
like image 645
rents Avatar asked Jun 02 '15 20:06

rents


People also ask

What is overflow multiplication?

Suppose we want to find the result after multiplying two numbers A and B. We have to check whether the multiplied value will exceed the 64-bit integer or not. If we multiply 100, and 200, it will not exceed, if we multiply 10000000000 and -10000000000, it will overflow.

What is an overflow in binary multiplication?

Overflow occurs when the product is larger than n bits. The longhand multiplication algorithm for n bit unsigned integers can be implemented using n bit addition. Observe that the least significant bit is determined by the first term in the sum.

How do you avoid overflow in multiplication in Java?

We can multiply recursively to overcome the difficulty of overflow. To multiply a*b, first calculate a*b/2 then add it twice. For calculating a*b/2 calculate a*b/4 and so on (similar to log n exponentiation algorithm).


2 Answers

In this case -

long m = 24 * 60 * 60 * 1000 * 1000;  

The right of the assignment is evaluated first. At right there is no long type data. All are int. So the JVM try to fit the result in an int then the overflow occurred.

And in the second case -

long m2 = 24L * 60 * 60 * 1000 * 1000;
long m3 = 24 * 60 * 60 * 1000 * 1000L;

Here one operand of the multiplication is long. So other are prompted to long automatically. The result is trying to fit to a long. Finally the assignment is done with m2 and m3.

And yes the associativity of multiplication from left to right - means the left operand is taken first. And Based on this fact I think in this scenario we should use -

long m2 = 24L * 60 * 60 * 1000 * 1000;  

this statement, since at this statement the promotion to long taken places earlier which reduces the risk of overflow.

like image 127
Razib Avatar answered Oct 17 '22 11:10

Razib


I would use the m2 line instead of the m3 line.

Java evaluates the multiplication operator * from left to right, so 24 * 60 is evaluated first.

It just so happens that 24 * 60 * 60 * 1000 (one 1000) doesn't overflow, so that by the time you multiply by 1000L (the second 1000), the product is promoted to long before multiplying, so that overflow doesn't take place.

But as you mentioned in your comments, more factors can cause overflow in the int data type before multiplying the last long number, yielding an incorrect answer. It's better to use a long literal for the first (left-most) number as in m2 to avoid overflow from the start. Alternatively, you can cast the first literal as a long, e.g. (long) 24 * 60 * ....

like image 30
rgettman Avatar answered Oct 17 '22 11:10

rgettman