Week 71: TAOCP 4.6.4 Evaluation of Polynomials

Evaluating polynomials efficiently: Horner's rule, evaluating at many points, preprocessing coefficients to save multiplications, and the related cost of matrix and polynomial operations, including the Fourier transform.

Time About 9 hours this week

Why it matters

Horner's rule is used in every math library and in hashing (polynomial rolling hashes). The FFT view connects to signal processing and fast multiplication.

Before you start

4.6.1 Division of Polynomials
4.3.3 How Fast Can We Multiply?

How to approach it

Implement Horner's rule and a rolling hash using it. Read the coefficient-preprocessing ideas lightly. Spend real time on the discrete Fourier transform discussion if FFT is new to you.

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

Numerical instability when evaluating with floats at large x.