Week 63 of 125
TAOCP 4.3.3 How Fast Can We Multiply?
Sign up or sign in to tick these off and give this week a due date.
-
Faster-than-schoolbook multiplication: splitting numbers in halves to trade a multiplication for additions (Karatsuba-style), Toom-Cook generalizations, and the Fourier transform approach that leads to Schonhage-Strassen.
Time About 9 hours this week
Why it matters
These ideas are behind every fast bignum library and are a beautiful example of divide and conquer and of how the FFT connects to arithmetic.
Before you start
- 4.3.1 The Classical Algorithms
- Divide and conquer, recursion
How to approach it
Implement the half-splitting method on top of your 4.3.1 bignums and find the crossover size where it beats schoolbook. Read the FFT part for ideas; implementing an FFT multiply is a stretch goal.
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
- Recursing all the way down to single digits. Switch to schoolbook below a threshold.
-
NeetCode LeetCode: 2 NeetCode 150 problems
Two problems from the NeetCode 150, in order. One box for the pair.