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

(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

Comments

  1. 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

Post a Comment

Popular posts from this blog

Java is Very Fast, If You Don’t Create Many Objects

System wide unique nanosecond timestamps

Comparing Approaches to Durability in Low Latency Messaging Queues