Fast Exponentiation
Square the base once per bit of the exponent, and multiply in on every 1 bit.
Decision · step 2 of 9Number Theory Basics: 3 to the 13, mod 7
This bit is 1, so multiply the current power in: 1 x 3 mod 7 = 3.
What you will see
The exponent's binary digits are consumed right to left; each 1 bit multiplies the accumulator.
Cost
| Best | O(log e) |
|---|---|
| Average | O(log e) |
| Worst | O(log e) |
| Space | O(1) |
How you work with it here
play it through, step one change at a time, run it on your own input.
Screen readers: Numbers announce their value and role; each step announces the arithmetic performed.
Reduced motion: Values crossfade; no travelling digits.
Before this
Related
Taught by the same lesson
Number Theory Basics covers these too, in the same run.