Week 70 of 125
TAOCP 4.6.3 Evaluation of Powers
Sign up or sign in to tick these off and give this week a due date.
-
Computing x^n with as few multiplications as possible: the binary (square-and-multiply) method, and the deep theory of addition chains, which ask for the shortest sequence of additions reaching n.
Time About 7 hours this week
Why it matters
Fast exponentiation is used everywhere from modular crypto to matrix powers for linear recurrences. Addition chains are a famous open-problem area that is easy to state.
Before you start
- 4.1 Positional Number Systems
How to approach it
Implement right-to-left and left-to-right binary exponentiation and count multiplications. Then find the shortest addition chain for small n by brute force and compare to the binary method.
Exercises
Work every exercise rated 10 to 20; most are about tracing the algorithm by hand or tweaking one step, which is exactly the skill you want. Pick one or two rated 20 to 25 that involve modifying the algorithm and implement your modification in a real language with tests. Skip HM exercises unless you enjoy calculus, and treat anything rated 40+ as a research problem, not homework.
Traps
- Assuming the binary method is optimal. Knuth shows small n where it is not.
-
NeetCode LeetCode: 2 NeetCode 150 problems
Two problems from the NeetCode 150, in order. One box for the pair.