modulo gives wrong result for big number in Java

Question

look at the below Java Code :

        long a = (long) 10e9+7;
        long b = (a * a);

        System.out.println("b is " + b);
        System.out.println("b%a is " + (b%a));

        System.out.println();


        BigInteger A = BigInteger.valueOf((long) 10e9+7);
        BigInteger B = A.multiply(A);


        System.out.println("B is " + B.longValue());
        System.out.println("B.mod(A) is " + B.mod(A));

Output:

b is 7766279771452241969
b%a is 6015846137   ///->> why ?? overflow 

B is 7766279771452241969 //// -> should not overflow 
B.mod(A) is 0

I was expecting % to give 0 in above case. But it gives some other numbers for the %

Can you show the value of `B`instead of `b`? I suspect overflow while calculating `b`. — Benoit, Jun 14 '23 at 14:40
You are clearly dealing with integer (or long) overflow. It should be obvious that 10e9+7 (which is 10000000007 in other notation) multiplied with itself will not result in a number that starts with 776..... — OH GOD SPIDERS, Jun 14 '23 at 14:40
Does this answer your question? [Incorrect Multiplication Result](https://stackoverflow.com/questions/23299070/incorrect-multiplication-result) — Chaosfire, Jun 14 '23 at 14:49
Did you mean `1.0e9+7`? That would actually work, since that number squared fits in a `long`. But `10e9+7` squared doesn't. Note that `10e9 == 1.0e10`. — k314159, Jun 14 '23 at 14:49

score 3 · Accepted Answer · answered Jun 14 '23 at 14:41

3

a * a overflows the value of Long.MAX_VALUE. As Benoit suggested in his comment, you're printing b twice. The value of B is not 7766279771452241969 but 100000000140000000049.

answered Jun 14 '23 at 14:41

Rob Spoor

6,186
1
19
20

CcmU · Answer 2 · 2023-06-14T16:35:04.990

First things first, long b = a * a overflows, since it should have the value 100.000.000.140.000.000.049 and it's greater than the max value of a signed long (2^63 - 1 = 9.223.372.036.854.775.807).

Secondly, I think it should be said that there are some differences between the two operation that you've used. As stated in the comments of this answer, java has the reminder operator % and does not provide a modulo operator or a function, like BigInteger does. Those are two slightly different things.

Mathematically if you want the result of c, given as c = a (mod b), it will be a number such that 1 < c < b (e.g. 4 (mod 3) = 1). Consequently, if b = a * a, then b (mod a) = a * a (mod a) = 0. If you want to read more about it, I suggest you to take a look at modular arithmetic.

The java reminder operator %, gives the reminder of the division (considering n % d), which has n as the numerator and d as the denominator. When mixing positive and negative numbers, there could be some inconsistencies with n (mod d), since

mod and remainder are actually semantically different operations

In conclusion, if you want to use modulo, you should rely on the functions provided from BigInteger, otherwise use the reminder operator. I also suggest this reading that explain the difference between modulus and reminder.

modulo gives wrong result for big number in Java

2 Answers2