Binary exponentiation: the idea
Prerequisites: Integer exponents, multiplication, and parity.
An exponent counts repeated multiplication. Binary exponentiation maintains an accumulator, a current base, and a remaining exponent. If the exponent is odd, it multiplies the accumulator by the base. It halves the exponent and squares the base for the next round. Each round processes one binary digit. The invariant is accumulator × base^remaining = originalBase^originalExponent.
Try it
Try 3 raised to 13. Its binary exponent is 1101, so only the set bits contribute factors. Compare multiplication count with multiplying by 3 thirteen times. Try exponent zero: the result is 1.
Reading the display
The state shows accumulator, current base, remaining exponent, and its binary digits. A history row follows each multiplication, shift, or square; the displayed invariant lets you follow the preserved result.
Time and memory
O(log e) arithmetic multiplications for positive exponent e and O(1) stored big integers. Bit-operation time and storage grow with the size of the numbers; multiplication is not constant cost for arbitrary precision.
The bounds above describe core work on prepared input. String conversion to code-point arrays and editor validation are additional work. The visualization saves the data at each operation so you can step backward. This recording requires extra time and memory beyond the algorithm’s own working storage. Input limits keep the demonstrations manageable.
When to use it—and what to watch
Uses BigInt internally and displays exact decimal strings. Large results cost more than the multiplication count alone suggests. This playground restricts the base to 1–20 and exponent to 0–20.
Continue exploring
- Euclidean algorithm — Find a greatest common divisor through successive remainders.
- Extended Euclidean algorithm — Find a GCD and coefficients explaining how the inputs produce it.
- Sieve of Eratosthenes — Cross out multiples and reveal every prime up to a limit.