An invariant makes exponent reduction safe.
Fast exponentiation can halve an even exponent after squaring the base, while an explicit product carries the unmatched factor from each odd step.
How can the exponent shrink quickly without changing the power being computed?
- Track base, exponent, and product as complete process state
- Square the base while halving an even exponent
- Move one base factor into product on an odd step
- Preserve product times base to the exponent as an invariant
At every call, product × base^exponent equals the original requested power. If exponent is even, replacing base with its square and exponent with half preserves that quantity. If exponent is odd, multiplying product by base and subtracting one from exponent preserves it instead.
The process stops when exponent reaches zero, because the remaining power is 1 and product already contains the answer. The history program records the full state at every call so each even and odd transition can be checked directly.
- Output
- —
- Value
- —
- Diagnostic
- —
The first program returns 1594323. The second returns ((2 10 1) (4 5 1) (4 4 4) (16 2 4) (256 1 4) (256 0 1024)).
Follow the even? decision before each transition. On even steps, base squares and exponent halves; on odd steps, product absorbs base and exponent decreases by one. The recorded states cover the exact selected integer inputs.
Change the program and compare the result.
Run fast-expt for 5 to exponent 11. Before running, list whether each exponent step is odd or even.
Show hint
An odd step subtracts one, making the next exponent even. An even step halves it.