Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

How Do I Calculate the Remainder for Extremely Large Exponential Numbers using Java?

DZone's Guide to

How Do I Calculate the Remainder for Extremely Large Exponential Numbers using Java?

· Java Zone
Free Resource

What every Java engineer should know about microservices: Reactive Microservices Architecture.  Brought to you in partnership with Lightbend.

This StackOverflow question asks

        How do i calculate the remainder for extremely large exponential numbers using java ? 
        eg. (48^26)/2401
I thought 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

Microservices for Java, explained. Revitalize your legacy systems (and your career) with Reactive Microservices Architecture, a free O'Reilly book. Brought to you in partnership with Lightbend.

Topics:

Published at DZone with permission of Peter Lawrey, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

THE DZONE NEWSLETTER

Dev Resources & Solutions Straight to Your Inbox

Thanks for subscribing!

Awesome! Check your inbox to verify your email so you can start receiving the latest in tech news and resources.

X

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}