CODEWITHSUNDEEP
java
user3276091
user3276091

Reputation: 263

How to get the remainder of a big numbers in java

is there any solution to this problem? why it returns 541 instead of 3.

public class Test {
    public static void main(String[] args) {
        double a = Math.pow(3, 561);

        // it returns 541 instead of 3
        System.out.println(a % 561);
    }
}

Upvotes: 4

Views: 1112

Answers (5)

Konstantin Yovkov
Konstantin Yovkov

Reputation: 62864

According to the Fermat's little theorem:

Math.pow(a, p) % p == a % p

and so:

Math.pow(3, 561) % 561 = 3 % 561 = 3

Therefore, you don't need to do this heavy calculations. Just maths.

Upvotes: 11

Marco13
Marco13

Reputation: 54639

The BigInteger class has a dedicated method for that:

import java.math.BigInteger;

public class BigModPow
{
    public static void main(String[] args)
    {
        BigInteger b = new BigInteger("3");
        BigInteger e = new BigInteger("561");
        BigInteger m = new BigInteger("560");
        BigInteger result = b.modPow(e, m);
        System.out.println(result);
    }
}

(EDIT: I changed the modulo to be not the same value as the exponent, to show that a non-trivial result is computed - although 561 is not a prime number)

Upvotes: 6

AlexR
AlexR

Reputation: 2408

If you want to compute something like
Math.pow(a, b) % m with minmal (not zero) loss of precision, use the modular exponentiation formula:
Math.pow(a, b) % m = Math.pow(a, b-1) % m * a
A Java recursive implementation would be:

private int modExp(int a, int b, int m) {
    if (b == 0) return 1;
    if (b == 1) return a % m;
    return (a * modExp(a, b-1, m)) % m;
}

This is still prone to overflow if a*(m-1) is too large for int. An alternative is BigInteger#modPow wich uses an equivalent algorithm.

Upvotes: 3

Ruchira Gayan Ranaweera
Ruchira Gayan Ranaweera

Reputation: 35557

Due to problem with double precision you will not get correct result with double. Use BigDecimal

 BigDecimal bigDecimal=new BigDecimal("3").pow(561);
 BigDecimal[] bigDecimal1=bigDecimal.divideAndRemainder(new BigDecimal("561"));
 System.out.println(bigDecimal1[1]);

divideAndRemainder() returns a two-element array containing the result of divide To Integral Value followed by the remainder. Remainder is part you are looking for.

Out put:

3

Upvotes: 3

Chris Martin
Chris Martin

Reputation: 30736

doubles don't actually behave as integers. Java's true integer type is java.math.BigInteger.

public static void main(String[] args) {
    BigInteger a = new BigInteger("3").pow(561);
    System.out.println(a.mod(new BigInteger("561")));
}

Upvotes: 6

Related Questions