Multiplying Large Number in java

Question

I am multiplying the 2 very large number in java , but the multiply output seems to be little strange
Code

long a =  2539586720l;
long b = 77284752003l;
a*=b;
System.out.println(a);
a=(long)1e12;
b=(long)1e12;
a*=b;
System.out.println(a);

Output:

-6642854965492867616
2003764205206896640

In the first case why the result is negative , if it's because of overflow then how come the result of second is positive ? Please explain this behavior ? Code

Edit:

I am using mod=100000000009 operation still it's negative ?

  a = ((a%mod)*(b%mod))%mod

This may be due to truncation as the result cannot be stored within a `long`. If `long` is not enough. Try using `BigInteger` — Jos, Jan 10 '17 at 17:37
@redflar3 that's not a issue , the main issue is why `negative` on first case while `positive ` on second case — Narendra Modi, Jan 10 '17 at 17:38
long can hold up to (2^63-1 which is 9e18) where as the result of your first multiplication exceeds 1e20. this causes truncation hence the result is not correct. similarly second result is also truncated as it should be 1e24. hence use BigInteger — Jos, Jan 10 '17 at 17:43
@redflar3 that's i want to understand why java is behaving like this , it should be `-ve` for both — Narendra Modi, Jan 10 '17 at 17:44
possible duplicate of http://stackoverflow.com/questions/7215411/multiplication-of-two-ints-overflowing-to-result-in-a-negative-number — dreamer, Jan 10 '17 at 17:50
https://docs.oracle.com/javase/specs/jls/se8/html/jls-15.html look for 15.17.1, search for `integer multiplication overflows` — Jos, Jan 10 '17 at 17:50

Nicolas Filotto · Answer 1 · 2017-01-10T18:44:54.917

The result that you get is typically an overflow issue, for a long: java allocates 63 bits for the number and the Most Significant Bit (MSB) for the sign (0 for positive values and 1 for negative values) so 64 bits in total.

So knowing that, Long.MAX_VALUE + 1 equals to -9223372036854775808 because Long.MAX_VALUE = 2^63 - 1 = 9223372036854775807 = 0x7fffffffffffffffL so if we add 1 to it, we get 0x8000000000000000L= Long.MIN_VALUE = -2^63 = -9223372036854775808. In this case the MSB switches from 0 to 1 so the result is negative which is actually what you get in the first use case.

If the MSB is set to 1 and you cause a new overflow with some computation, it will switch to 0 again (because we keep only the first 64 bits) so the result will be positive, which is actually what you get in the second use case.

To avoid that you need to use BigInteger.

score 2 · Answer 2 · answered Jan 10 '17 at 17:47

Yes. It is an overflow issue. The long size is 8 bytes and the range goes from -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807

If you want to multiply really big numbers. Use BigInteger

import java.math.*;

public static void main(String[] args){
    BigInteger bi1, bi2, bi3;

    bi1 = new BigInteger("2539586720"); //or 1000000000000
    bi2 = new BigInteger("77284752003"); 

    // multiply bi1 with bi2 and assign result to bi3
    bi3 = bi1.multiply(bi2);

    String str = bi1 + " * " + bi2 + " = " +bi3;
    //Multiplication result is 2539586720 * 77284752003 = 196271329845312200160
}

Import `java.math.BigInteger` not `*` – Michael Jan 10 '17 at 17:54 — Michael, Jan 10 '17 at 17:54

score 0 · Answer 3 · answered Jan 10 '17 at 17:53

As per JLS 15.17.1

If an integer multiplication overflows, then the result is the low-order bits of the mathematical product as represented in some sufficiently large two's-complement format. As a result, if overflow occurs, then the sign of the result may not be the same as the sign of the mathematical product of the two operand values.

This is why you are getting negative values and doesn't have any correlation with the input numbers. This is because of the fact that long in Java can represent only from -2^63 to (2^63)-1 and your result is greater than this.

In order to avoid this issue, when dealing with large number arithmetic, you should always use BigInteger. A sample code is given below

BigInteger.valueOf(123L).multiply(BigInteger.valueOf(456L));

score 0 · Answer 4 · answered Jan 10 '17 at 17:55

In regards to the behavior, both are examples are overflows. The fact that one answer is negative does not add any special meaning. The first set of numbers you multipled happen to result in a long whose most significant bit is 1, while the latter set didn't.

Multiplying Large Number in java

4 Answers4

Linked

Related