### How do I calculate the remainder for extremely large exponential numbers using Java?

This StackOverflow question asks

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

eg. (48^26)/2401

I though the answer was worth reproducing as there is a surprisingly simple solution.

An answer is to modulus the value in each iteration of calculating the power

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

eg. (48^26)/2401

I though the answer was worth reproducing as there is a surprisingly simple solution.

An answer is to modulus the value in each iteration of calculating the power

```
(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
```

Hi, how did you colorize the Java code? I see that the formulas given are not colorized -- how are they formatted? The reason I ask is that I'm interested in writing a blog which will have some code in it, so I'm looking around to see how other blogs have displayed code. Thanks for any info.

ReplyDelete