Motivation
Let’s take a look at how we multiply two polynomials of degree \(N\): \[\begin{align*} f(x) &= 4x^{4}-2x^{3}-6x^{2}\ +4x\ +\ 3\\ g(x) &= -x^{4}+11x^{3}-9x^{2}+-1x\ +\ 6\\ \end{align*}\]
We can use the distributive property to multiply two polynomials and then sum up coefficients for identical terms. \[\begin{align*} f(x) &\cdot g(x) = \\ (4x^{4}-2x^{3}-6x^{2}\ +4x\ +\ 3) &\cdot (-x^{4}+11x^{3}-9x^{2}+-1x\ +\ 6) = \\ -4x^{8}+46x^{7}-52x^{6}-56x^{5} &+ 121x^{4}-9x^{3}-67x^{2}+21x+18 \end{align*}\]
However, this leads to \(O(N^2)\) operations to compute the coefficients. In this section, we are going to look at how we can accomplish polynomial multiplication in \(O(NlogN)\) using Fast Fourier Transform (FFT) (an algorithm to compute DFT). We will also look at how we can solve this problem in ~10 lines of code!
Polynomial Representations
A polynomial of degree \(n-1\) can be represented via:
... continue reading