Задача
Даны два полинома: $$$A = a_{0} + a_{1} \cdot x + \dots + a_{n-1} \cdot x^{n-1}$$$ и $$$B = b_{0} + b_{1} \cdot x + \dots + b_{n-1} \cdot x^{n-1}$$$. Для удобства будем записывать их как $$$[a_{0}, a_{1}, \cdot a_{n-1}]$$$ и $$$[b_{0}, b_{1}, \cdot b_{n-1}]$$$. Необходимо найти полином $$$C = A \cdot B$$$. Его размер равен $$$2n$$$.
Тривиальное решение
Задачу можно решить за асимптотику $$$O(n^{2})$$$, напрямую посчитав $$$C = A \cdot B = [a_{0} \cdot b_{0}, a_{0} \cdot b_{1} + a_{1} \cdot b_{0}, \dots ] = [\sum\limits_{i \in [0,0]}(a_{i} \cdot b_{0-i}), \sum\limits_{i \in [0,1]}(a_{i} \cdot b_{1-i}), \dots, \sum\limits_{i \in [0,k]}(a_{i} \cdot b_{k-i}), \dots]$$$.
План решения
Решение с помощью быстрого преобразования Фурье будет состоять из трех шагов:
Вычислить $$$A(x_{0}), A(x_{1}), \dots A(x_{2n-1})$$$ и $$$B(x_{0}), B(x_{1}), \dots B(x_{2n-1})$$$.
Вычислить значение $$$C$$$ в точках: $$$C(x_{0}) = A(x_{0}) \cdot B(x_{0}), C(x_{1}) = A(x_{1}) \cdot B(x_{1}), \dots C(x_{2n-1}) = A(x_{2n-1}) \cdot B(x_{2n-1})$$$.
Интерполировать $$$C$$$ по известным $$$2n$$$ значениям.
Вычисление значения полинома в точке в общем случае решается за $$$O(n)$$$. Поэтому первый шаг требует $$$O(n^{2})$$$ действий. Второй шаг решается одним проходом по массивам за $$$O(n)$$$. Интерполяция полинома решается в общем случае за $$$O(n^{2})$$$ с помощью интерполяционной формулы Лагранжа. Итоговая асимптотика решения для произвольных $$$x_{0}, x_{1}, \dots x_{2n-1}$$$ — $$$O(n^{2})$$$. Количество действий может быть существенно уменьшено, если выбрать $$$x_{0}, x_{1}, \dots x_{2n-1}$$$ особым образом.
Выбор множества для $$$X$$$
Рассмотрим множество $$$S$$$ комплексных чисел, модуль которых равен $$$1$$$. На комплексной плоскости ГМТ множества $$$S$$$ — окружность радиуса $$$1$$$ с центром в начале координат. Будем обозначать элемент множества $$$S$$$, аргумент которого равен $$$\phi$$$, как $$$\overline{\phi}$$$. Данное множество обладает замечательным свойством, на которое мы и будем опираться при написании алгоритма:
Теорема: Для $$$n \in \mathbb{Z}$$$ верно $$$(\overline{\phi})^{n} = \overline{n\phi}$$$.
Доказательство: докажем с помощью математической индукции. Для $$$n=0$$$ утверждение очевидно. Пусть утверждение верно для $$$n=k$$$. Докажем, что оно верно для $$$n=k+1$$$ и для $$$n=k-1$$$. $$$(\overline{\phi})^{k+1} = (\overline{\phi})^{k} \cdot \overline{\phi} = \overline{k\phi} \cdot \overline{\phi}$$$. Известно, что при перемножении комплексных чисел их модули перемножаются, а аргументы складываются. Поэтому $$$\overline{k\phi} \cdot \overline{\phi} = \overline {(k+1)\phi}$$$. Аналогично $$$(\overline{\phi})^{k-1} = \overline{k\phi} / \overline{\phi}$$$. Известно, что при делении комплексных чисел их модули делятся, а аргументы вычитаются. Поэтому $$$\overline{k\phi} / \overline{\phi} = \overline {(k-1)\phi}$$$.
Основной смысл этой теоремы — тот факт, что мы можем заменить степени на суммы. Кроме того, если выбрать в качестве множества $$$X$$$ точек числа $$$\overline{\frac{0 \cdot 2\pi}{2n}}, \overline{\frac{1 \cdot 2\pi}{2n}}, \dots \overline{\frac{(2n-1) \cdot 2\pi}{2n}}$$$, то любое число из этого множества в произвольной целой степени будет в этом множестве (говорят, множество $$$X$$$ замкнуто относительно операции целой степени).
Быстрое преобразование Фурье
Задача: дан многочлен $$$A = [a_{0}, a_{1}, \dots a_{n-1}]$$$. Необходимо вычислить $$$A(\overline{\frac{0 \cdot 2\pi}{n}}), A(\overline{\frac{1 \cdot 2\pi}{n}}), \dots A(\overline{\frac{(n-1) \cdot 2\pi}{n}})$$$. (Важно: выше мы вычисляли значения функция в $$$2n$$$ точках, так как нам необходимо знать $$$2n$$$ значений полинома $$$C$$$. Сейчас же мы вычислим значения в $$$n$$$ точках, а перед вызовом этого алгоритма просто допишем к $$$A$$$ $$$n$$$ нулей.) Для удобства будем считать $$$n$$$ целой степенью числа $$$2$$$.
Решение:
Будем решать задачу рекурсивно. Для $$$n=1$$$ нам необходимо вычислить массив из одного элемента $$$A(\overline{0}) = A(1) = a_{0}$$$. Пусть теперь $$$n \ge 2$$$. Заметим, что $$$A(x) = a_{0}x^{0} + a_{1}x^{1} + \dots + a_{n-1}x^{n-1} = (a_{0} + a_{2}x^{2} + a_{4}x^{4} + \dots + a_{n-2}x^{n-2}) + x(a_{1} + a_{3}x^{2} + a_{5}x^{4} + \dots + a_{n-1}x^{n-2})$$$. Пусть $$$A_{1} = [a_{0}, a_{2}, a_{4}, \dots a_{n-2}]$$$ и $$$A_{2} = [a_{1}, a_{3}, a_{5}, \dots a_{n-1}]$$$. Тогда $$$A(x) = A_{1}(x^{2}) + x A_{2}(x^2)$$$. Кажется, что члены $$$x^{2k}$$$ усложняют задачу, но согласно теореме выше это $$$2kx$$$! Поэтому $$$A(x) = A_{1}(2x) + x A_{2}(2x)$$$.
Предположим, у нас есть алгоритм, решающий задачу для $$$n=\frac{k}{2}$$$. Решим задачу для $$$n=k$$$. Построим массивы $$$A_{1}$$$ и $$$A_{2}$$$ по определению выше и вызовем БПФ для них. Согласно предположению, мы умеем это делать. Теперь необходимо простроить БПФ для $$$A$$$. Пусть в массивах $$$B_{1}$$$ и $$$B_{2}$$$ лежат БПФ от них $$$A_{1}$$$ и $$$A_{2}$$$. Вспомним, что это $$$B_{1} = [A_{1}(\overline{\frac{0 \cdot 2\pi}{\frac{k}{2}}}), A_{1}(\overline{\frac{1 \cdot 2\pi}{\frac{k}{2}}}), \dots A_{1}(\overline{\frac{(\frac{k}{2}-1) \cdot 2\pi}{\frac{k}{2}}})]$$$ и $$$B_{2} = [A_{2}(\overline{\frac{0 \cdot 2\pi}{\frac{k}{2}}}), A_{2}(\overline{\frac{1 \cdot 2\pi}{\frac{k}{2}}}), \dots A_{2}(\overline{\frac{(\frac{k}{2}-1) \cdot 2\pi}{\frac{k}{2}}})]$$$. То есть, это значения полиномов $$$A_{1}$$$ и $$$A_{2}$$$ в $$$\frac{k}{2}$$$ точках равномерно распределенных по окружности комплексной плоскости. Пусть $$$B$$$ — результат БПФ для $$$A$$$. Заполним этот массив: $$$B[i] = A(\overline{\frac{i \cdot 2\pi}{k}}) = A_{1}(\overline{\frac{2i \cdot 2\pi}{k}}) + \overline{\frac{i \cdot 2\pi}{k}} \cdot A_{2}(\overline{\frac{2i \cdot 2\pi}{k}}) = A_{1}(\overline{\frac{i \cdot 2\pi}{\frac{k}{2}}}) + \overline{\frac{i \cdot 2\pi}{k}} \cdot A_{2}(\overline{\frac{i \cdot 2\pi}{\frac{k}{2}}}) = B_{1}[i] + \overline{\frac{i \cdot 2\pi}{k}} \cdot B_{2}[i]$$$.
