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. Robert Dodier27 November 2013 at 18:58

    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

Why You Should Tune Code Before Your Garbage Collector

Image
Optimising your memory allocations in Java could make far more difference than your choice of Garbage Collector and may even change which is the best garbage collector. In this post I look at a simple event to response latency benchmark, MarketDataSnapshot to NewOrderSingle at 50K/s for 30 minutes using JLBH to test Chronicle-FIX. The goal is to compare a system which is doing redundant work (in this case logging each message using SLF4J), compared with not logging (Chronicle-FIX records every message internally using Chronicle Queue) and how this changes the choice of Garbage Collector For the p99 (worst 1 in 100) the choice of Garbage Collector makes a different on par with optimising how loggin is done However, for the p99.99 (worst 1 in 10,000) optimsing how the logging is done is orders of magnitude more signifciant than the choice of Garbage Collector Unoptimised Benchmark This takes the optimised benchmark and adds one SLF4J log line of just ...
Read more

Asking multiple AI to optimise the same code

As different AIs are implemented differently, they don't all provide the same answer, nor do they consistently outperform one another. The best approach is to use multiple AI and pick the one you like best. My goal here is not to declare a winner based on one example, but instead to show the variety of answers you can get with different AI. I asked each AI to Suggest how to implement this more optimally private static String formatOffset(int millis) { String sign = millis < 0 ? "-" : "+"; int saveSecs = Math.abs(millis) / 1000; int hours = saveSecs / 3600; int mins = ((saveSecs / 60) % 60); int secs = (saveSecs % 60); if (secs == 0) { if (mins == 0) { return sign + twoDigitString(hours); } return sign + twoDigitString(hours) + twoDigitString(mins); } return sign + twoDigitString(hours) + twoDigitString(mins) + twoDigitString(secs); } private static String twoDigitString(int value) { ...
Read more

Which Doc Format is Best for AI Specifications?

I have a Spec Driven Project with 674 documents incl 181 specs, 429 tasks, and 40 project docs. About 1/3 of these are an acceptance sub-project to show the root project meets fit-for-purpose requirements. I used Fable to convert these to and from AsciiDoc, Markdown, and HTML. From this, I tried to draw some conclusions about which format is better than the others for AI specifications. TL;DR: Markdown for AI working documents, AsciiDoc for curated human-reviewed specs, HTML only as a publishing target. Objective Metrics Corpus Tokens (Approx) Markdown: 594k, AsciiDoc: 598K, HTML: 661k Worst Single-File Ratio AsciiDoc: 1.023x, HTML: 1.26x (due to tables and code blocks) Markup share of file content Markdown 0.9%, AsciiDoc 1.3%, HTML 9.9% - a 10x overhead for HTML Read/write Assessment In terms of readability, both Markdown and AsciiDoc are good. HTML has far more tags, which add noise. One of the most common tags is <code> some code </c...
Read more