3 ms·
That starts it small, but doesn't necessarily keep it small. For instance, if n is 1000 and the mod is 1001, we still end up with 1,000,000,000,000 as an interm
by Jtsummers 6y ago
That starts it small, but doesn't necessarily keep it small. For instance, if n is 1000 and the mod is 1001, we still end up with 1,000,000,000,000 as an intermediate value before the final mod 1001. That's not too bad (fits in a 64-bit integer), but it's easy to see how (with different exponents or bases) it can still blow up. The second python example in GP comment keeps it small by making use of the mod as it steps through the exponentiation, not just at the start and end.
EDIT: What I wrote was more about the general case. In this specific case, the largest number we get after modulo would be 14, and 14^4 is only 38,416 so it does actually stay small for this specific instance of the problem.
- ChrisLomont 6y agoYou don't have to do the power all at once - use powermod - then you need at most a square to fit. And when that doesn't fit, there are still more math tricks to keep it small and fast.