Problem: Compute the product of two polynomials efficiently. Solution: Discussion: The Fourier Transform has a lot of applications to science, and I’ve covered it on this blog before, see the Signal Processing section of Main Content. But it also has applications to fast computational mathematics. The naive algorithm for multiplying two polynomials is the “grade-school” […]...