CODEWITHSUNDEEP
javanumbers
BaraDos
BaraDos

Reputation: 13

Arithmetic mistakes when dealing with large numbers in java

I'm working with some arithmetic operations in Java which need to process very large numbers.

See this simple code snippet:

// A = a^k mod p 

    double k = 96 , a = 13 , p = 353 ;
    double A = (Math.pow(a,k))%p;
    System.out.println(A);

This prints 29.0.

When I use my windows calculator, it returns 58.0 for (13^96) % 353. I know that the calculator is correct.

Why does this Java code print an incorrect result?

Upvotes: 0

Views: 218

Answers (2)

Hermann Döppes
Hermann Döppes

Reputation: 1373

Explanation

Well, Math.pow probably does not do what you think it does. This is not your fault, it's practically lying to you. It returns a double that is reasonably close to 13^96, but not exactly. Since we are talking a number around 10^107 here, a small relative change means an absolute change far larger than 353. So, all bets about this are off.

Example

To put more numbers to this, practically the same problem arises when we use decimal scientific notation: The quotient is practically one but the difference is around 2^91. In general, floating point numbers are unsuitable for integer arithmetic, you are practically bound to get these problems.

Solution

While a big integer lib would work, there is a more grounded way to approach this: Perform binary exponentiation and take the modulus each step. In case you're a beginner, this will teach you more than the black box of some big int lib.

Upvotes: 3

azro
azro

Reputation: 54148

The calcul 13^96 result in the number : 

86808413954902578113899124146033582025796522106191700214004730205740649831517648547259748010923363334343041

which requires too much precision to be stored in a double type

You can do this with BigInteger : 

BigInteger bK = new BigInteger("96");
BigInteger bA = new BigInteger("13");
BigInteger bP = new BigInteger("353");
BigInteger res = bA.modPow(bK, bP);    // same as  res = bA.pow(96).mod(bP);
System.out.println(res);               // 58

Upvotes: 1

Related Questions