How do i calculate the remainder for extremely large exponential numbers using java?

Question

How do i calculate the remainder for extremely large exponential numbers using java ? eg. (48^26)/2401

I tried using BIGINTEGER, however it gave the same output for large divisors.I'm not sure if BIG INTEGER can do this .I have tried all other PRIMITIVE data type.They seem to be insufficient.

FYI it tried the following code:

BigInteger a = new BigInteger("48");
a = a.pow(26);
BigInteger b = new BigInteger("2401");//49*49
a = a.mod(b);
System.out.println(a);

I don't know why i got the same output everytime, it's weird that it's working fine now. The answer comes out to be 1128

Answer 1

You can use repeated modulus of smaller numbers.

say you have

(a * b) % n
((A * n + AA) * (B * n + BB)) % n                     | AA = a %n & BB = b % n
(A * B * n^2 + A * N * BB + AA * B * n + AA * BB) % n
AA * BB % n                                           since x * n % n == 0
(a % n) * (b % n) % n

In your case, you can write

48^26 % 2401
(48^2) ^ 13 % 2401

as

int n = 48;
for (int i = 1; i < 26; i++)
    n = (n * 48) % 2401;
System.out.println(n);

int n2 = 48 * 48;
for (int i = 1; i < 13; i++)
    n2 = (n2 * 48 * 48) % 2401;
System.out.println(n2);

System.out.println(BigInteger.valueOf(48).pow(26).mod(BigInteger.valueOf(2401)));

prints

1128
1128
1128

As @Ruchina points out, your example is small enough to calculate using a simple double expression.

for (int i = 1; i < 100; i++) {
    BigInteger mod = BigInteger.valueOf(48).pow(i).mod(BigInteger.valueOf(2401));
    double x = Math.pow(48, i) % 2401;
    if (mod.intValue() != x) {
        System.out.println(i + ": " + mod + " vs " + x);
        break;
    }
}

prints

34: 736 vs 839.0

In other words, any power of 48 is fine up to 33.

Answer 2

This worked for me.

import java.math.BigInteger;


public class BigMod{
        public static void main (String[] args){
                BigInteger b1 = new BigInteger ("48");
                BigInteger b2 = new BigInteger ("2401");
                BigInteger b3 = b1.pow(26);
                BigInteger result = b3.mod(b2);
                System.out.println(result);
        }
}

Not sure what trouble you're having with BigInteger. Can you explain what didn't work?

Answer 3

Use BigInteger.modPow().

BigInteger a = new BigInteger("48");
BigInteger b = new BigInteger("26");
BigInteger c = new BigInteger("2401");

BigInteger answer = a.modPow(b, c);

The answer will be 1128. Note that BigInteger is immutable so objects a, b, and c can not be modified.

Answer 4

You don't even need a BigInteger for this, you can calculate that value using BigMod divide and conquer algorithm taking advantage of the following property of the mod operation

(A * B) mod n = ((A mod n) * (B mod n)) mod n

Then (B ^ c) mod n can be viewed as a special case of the property:

(B ^ c) mod n = ((B mod n) * (B mod n) ... c times) mod n

The following code does the calculation:

public class BigModExample { 
    public static long bigMod(long  b, long  c, int n) {
        if (c == 0) {
            return 1;
        }

        // Returns: (b ^ c/2) mod n
        long b2 = bigMod(b, c / 2, n);        

        // Even exponent
        if ((c & 1) == 0) {
            // [((b ^ c/2) mod n) * ((b ^ c/2) mod n)] mod n
            return (b2 * b2) % n;
        } else {
            // Odd exponent
            // [(b mod n) * ((b ^ c/2) mod n) * ((b ^ c/2) mod n)] mod n
            return ((b % n) * (b2 * b2)) % n;
        }
    }

    public static void main(String... args) {
        System.out.println(bigMod(48, 26, 2401));
    }
}

Prints

1128

Answer 5

Further explanation on Peter Lawrey's solution.

(a*b)%n
= ((A*n + AA) * (B*n + BB))%n where a=A*n+AA, AA=a%n & b=B*n+BB, BB=b%n
= (A*B*n^2 + A*n*BB + AA*B*n + AA*BB)%n
= (AA*BB)%n
= (a%n * b%n)%n

(a^c)%n
= (a^(c-1) * a)%n
= ((a^(c-1))%n * a%n)%n
= ((a^(c-2)*a)%n * a%n)%n
= ((a^(c-2)%n * a%n)%n * a%n)%n

Example1: when c is 3

(a^3)%n
= ((a^2)*a)%n
= ((a^2)%n * a%n)%n
= ((a*a)%n * a%n)%n 
= ((a%n * a%n)%n * a%n)%n

Example2: when c is 4

(a^4)%n
= ((a^3)*a)%n
= ((a^3)%n * a%n)%n
= ((a^2 * a)%n * a%n)%n
= (((a^2)%n * a%n)%n * a%n)%n
= (((a*a)%n * a%n)%n * a%n)%n
= ((a%n * a%n)%n * a%n)%n * a%n)%n

java code:

int a = 48;
int c = 26;
int n = 2401;
int a_mod_n = a%n;
int result = a_mod_n;
for (int i = 1; i < c; i++) {
    result = (result * a_mod_n) % n;
}
System.out.println("result: " + result);

48 is ambiguous as both a and a%n are 48. The above Java code strictly follows the equation ((a^(c-2)%n * a%n)%n * a%n)%n so that it is easier to understand.

Answer 6

 BigDecimal b= BigDecimal.valueOf(Math.pow(48,26) %2401);

output b = 1128.0

Answer 7

Try using a BigDecimal for large decimal numbers. It is not prone to errors like double and float because of the way it's data is stored. Also, it has a (potentially) infinite amount of decimal places.