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

Answer 1

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.