tags:

• dnc

7. Fast Polynomial Multiplication #

Created Tue Jul 30, 2024 at 12:30 AM

180-182 The fast convolution algorithm uses divide and conquer, but a detailed proof of correctness relies on fairly sophisticated properties of complex numbers and linear algebra that are beyond the scope of what I want to do here.

• Any polynomial can be represented as a set of points.
• Its easier to work with points, and DnC becomes applicable.