

%magic to do it work

\Section{Быстрое проеобразование Фурье}{6 мая}{Лобанов Артём}

\Subsection{Немного о многочленах}

Давайте в рамках этого конспекта под \emph{степенью} многочлена понимать количество коэффициентов (т.е. старшая степень + 1). 
Известно, что в поле комплексных чисел между многочленами \emph{степени} не больше $n$ и наборами их значений в $n$ точках существует биекция. 
    
\Subsection{Идея}

Пусть у нас есть два многочлена $P$ и $Q$ степеней $n$ и $m$. Мы хотим их перемножить. Степень их произведения будет $m + n - 1$. 
Если мы посчитаем значения многочлена $T = PQ$ в $m + n - 1$ точке, то по ним мы сможем однозначно восстановить $T$.
Чтобы узнать значение $T$ в точке $x$ достаточно перемножить значения $P$ и $Q$ в точке $x$.
Итак, алгоритм: считаем значения $P$ и $Q$  в достаточно большом количестве точек, перемножаем их, по полученным точкам восстанавливаем многочлен $T$. 
Хотя зачем нам всё это? Считать значения многочлена степни $n$ в $n$ точках, да ещё и потом обратно восстанавливать...
Это ж долго! А за квадрат можно и в столбик было перемножить. 

\Subsection{Мотивация}

Оказывается, если брать не какие-то точки, а специальные, то посчитать значения и восстановить по ним многочлен можно быстро, за $\O(n \log n)$.
Преобразование из массива коэффициентов многочлена в значения этого многочлена в \emph{этих точках} называется дискретным преобразованием Фурье.

\Subsection{Быстрое преобразование Фурье}

\t{//} Напомним, что $e^{ix} = \cos x + i \sin x$

\t{//} $(e^{ix})^n = e^{ixn}$

Пусть $P$ -- многочлен степени $n$. 
Пусть $n$ -- степень двойки (если нет, дополним до ближайшей сверху). 
Посчитаем значения $P$ в точках $e^{-\mfrac{2 \Pi i}{n}j}$ для всех $j$ от $0$ до $n{-}1$.
Обозначим за $P_0$ -- многочлен из коэффициентов $P$ с чётными номерами, $P_1$ -- с нечётными. 
Например, $$P = 10 + 1x + 2x^2 + 3x^3 + 4x^4 + 5x^5 + 6x^6 + 7x^7$$ $$P_0 = 10 + 2x + 4x^2 + 6x^3$$ $$P_1 = 1 + 3x + 5x^2 + 7x^3$$.

Методом пристального взгляда поймём, что $P(x) = P_0(x^2) + xP_1(x^2)$.  

Точки, в которых мы считаем значения, являются корнями $2^k$-ой степени из 1. 
При возведении в квадрат они, внезапно, превращаются в корни $2^{k-1}$-степени из 1 
(в следствие периодичности sin/cos, квадраты $j$-ого и $(j+2^{k-1})$-ого по номерам корней совпадут).
Степени $P_0$ и $P_1$ -- $2^{k - 1}$. Мы хотим посчитать их значения в корнях $2^{k - 1}$-степени из 1. 
А как раз это мы умеем находить быстрым преобразованием Фурье (рекурсивный вызов).
Зная значения $P_0$ и $P_1$ в нужных точках, можно за линию найти значения $P$.
Глубина рекурсии -- $\O(\log n)$. На каждом в сумме уровне $\O(n)$ операций. Тогда время работы $\O(n \log n)$.


\Subsection{Медленная реализация БПФ}

Ниже приведён псевдокод быстрого преобразования фурье и умножения многочленов через него. 
Эту реализацию можно сильно соптимизировать. Об этом нам расскажут в следующих конспектах.

\lstinputlisting{lobanov/fft.cpp}



 