\Section{Действительно Быстрое проеобразование Фурье}{6 травня}{Егор Щербин}

Приведённый выше код БПФ за $\O(n\log n)$ решает поставленную задачу, но есть
несколько недостатков:

\begin{itemize}
\item
    По-настоящему быстрым его назвать нельзя;
\item
    Непонятно, почему обратное преобразование вообще корректно работает.
\end{itemize}

\begin{THE}{\textit{Комментарий}}

    \textit{Но где доказательства?}
\end{THE}

\Subsection{Фурье обращается просто}

Начнём с обращения. Пусть $w=e^{\frac{2\pi i}n}$, $a_i$ "--- коэффициенты
многочлена, а $f_i$ "--- его значение в точке $w_i$. Заметим, что:

$$f_0=a_0+a_1w^0+a_2w^0+a_3w^0+\dots$$
$$f_1=a_0+a_1w^1+a_2w^2+a_3w^3+\dots$$
$$f_2=a_0+a_1w^2+a_2w^4+a_3w^6+\dots$$
$$f_3=a_0+a_1w^3+a_2w^6+a_3w^9+\dots$$

и так далее...

\begin{Lm}
    $\sum f_i=a_0\cdot n$
    \proof
    Действительно, можно понять, что в каждом столбце, кроме первого сумма равна
    нулю. Сумма в $k$-м столбце:

    $$a_k(1+w^k+w^{2k}+\dots+w^{k(n-1)})=a_k\dfrac{1-w^{kn}}{1-w}=0$$
\end{Lm}

\begin{Lm}
    $\sum\limits_{i=0}^{n-1} f_iw^{-ik}=a_k\cdot n$
    \proof

    В $j$-м столце слагаемые приняли вид $a_iw^{i(j-k)}$. В $k$-м столбце
    сумма, очевидно, равна $a_k\cdot n$, а в остальных, аналогично
    доказательству предыдущей леммы, "--- $0$.
\end{Lm}

Как мы видим, обратное преобразование действительно очень похоже на прямое,
осталось только понять, что $w^{-k}=w^{n-k}$, поэтому после прямого 
преобразования мы получим $(a_0,a_{n-1},\dots,a_1)$, следовательно, нужно
развернуть элементы со второго по последний.

\begin{THE}{\textit{Комментарий}}

    \textit{Вы понимаете, о чём говорят все эти люди? Я нет.}
\end{THE}

\Subsection{Фурье погрешен}

Пусть мы коэффициенты перемножаемых многочленов не больше $M$, тогда
коэффициенты произведения не больше $nM^2$. Ясно, что, чтобы алгоритм корректно 
посчитал результат, используя тип \t{double} для хранения вещественной и мнимой 
частей комплексных чисел, необходимо, чтобы эта величина не превосходила 
$10^{15}$ (для \t{long double} "--- $10^{18}$). Но можно сказать кое-что 
поточнее.

\begin{THEE}{Эмпирический факт}
    Если $nM^2\leqslant 10^{16}$, то всё на ура посчитается в \t{long double}
    с ошибкой, по модулю меньшей $0.5$ (то есть округление до целого
    будет работать корректно).
\end{THEE}

\begin{THE}{\textit{Комментарий}}

    \textit{Сильное заявление. Проверять я его, конечно, не буду.}
\end{THE}

\Subsection{Коротко о длинных числах}

Заметим несколько вещей:

\begin{enumerate}
\item
    Длинные целые числа "--- те же многочлены, только уже вычисленные в точке 
    $BASE$ (основание системы счисления), следовательно их можно перемножать 
    абсолютно так же. Следует, однако, не забыть сделать переносы в старшие 
    разряды.
\item
    Вещественные числа "--- те же целые числа, только домноженные на 
    $BASE^{-k}$, следовательно проблем с их перемножением тоже быть не должно.
\item
    Наконец, можно упомянуть, что в STL уже реализованы комплексные числа, 
    называются они \t{std::complex}. Тем не менее, собственноручно написанная
    реализация комплексных чисел будет почему-то работать быстрее.
\end{enumerate}

\begin{THE}{\textit{Комментарий}}

    \textit{Я не хочу этот банан.}
\end{THE}

\Subsection{Фурье оптимизируется и избавляется от ненужной рекурсии}

\Subsubsection{$2\R=1\mathbb{C}$}

До сих пор мы БПФ, работающему с комплексными числами давали на вход
вещественные числа и игнорировали комплексную часть. Пора исправить это 
недоразумение.

Пусть мы хотим сделать ДПФ для вещественных последовательностей $a_j$ и $b_j$. 
Построим  последовательность $c_j=a_j+ib_j$. Посчитаем по нему ДПФ и, получив 
$fc_j$, хотим посчитать $fa_j$ и $fb_j$.

\begin{Lm}
    $$fa_j=\frac12(fc_j+\overline{fc_{n-j}})$$
    $$fb_j=\frac1{2i}(fc_j-\overline{fc_{n-j}})$$
    \proof
    $$fc_j=c(w^j)=a(w^j)+ib(w^j)=fa_j+ifb_j$$
    $$\overline{fc_{n-j}}=\overline{a(w^{n-j})}+\overline{ib(w^{n-j})}=
    a(w^j)-ib(w^j)=fa_j-ifb_j$$
\end{Lm}

Таким образом, мы из двух запусков БПФ сделали один, ну это ли не чудо?

\begin{THE}{\textit{Комментарий}}

    \textit{Звучит неплохо.}
\end{THE}

\Subsubsection{$\cos$ и $\sin$ "--- долгая штука}

Каждый раз вычислять $w^k$ слишком долго, ведь $e^{ix}=\cos x + i\sin x$, а
вычисление тригонометрических функций занимает время. К счастью, так как мы
хотим всегда вычислять корни из 1 степени $2^k$, мы можем предпосчитать в
массиве \t{root} корни степени $n$, а корни других степеней уже будут в этом
массиве.

\begin{THE}{\textit{Комментарий}}

    \textit{Честно сказать, не хочется комментировать эту ситуацию.}
\end{THE}

\Subsubsection{Нерекурсивная реализация}

На первом шаге БПФ по данному массиву создаёт два: из коэффициентов с чётными
номерами и из коэффициентов с нечётными. А давайте не будем создавать новые
массивы, а просто поместим первый из них в левую половинку исходного массива,
а второй "--- в правую. На следующих шагах будем действовать аналогично, более
того, потребуем, чтобы результат вызова БПФ лежал на месте входного массива.

Мы получили inplace алгоритм, но не будем останавливаться на достигнутом.
Заметим, что при спуске в рекурсии происходит перестановка элементов массива, а
при подъёме "--- комбинация двух результатов следующего уровня. Сейчас мы
избавимся от спуска, сразу переставив элементы на их окончательные места, и 
сделаем один подъём, комбинируя результаты параллельно.

Нетрудно понять, что $i$-й элемент переход на место $rev[i]$, где $rev[i]$ "---
число полученное разворотом битовой записи числа $i$. Вот как считать $rev[i]$:
\begin{code}
for i = 1..n-1
    rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << k) // k = log n
\end{code}

Подъём будет производиться в несколько шагов, на $t$-м шаге части длины $2^t$
будут попарно объединяться в части длины $2^{t+1}$. Впрочем, хватит слов, 
прочитайте код, и всё сразу станет ясно.

\lstinputlisting{shcherbin/fft.cpp}

\begin{THE}{\textit{Комментарий}}

    \textit{У меня есть запасной вариант, и я им воспользуюсь.}
\end{THE}
