1632
правки
Изменения
м
\dfracn{a_0}{n}\\\dfracn{a_{n-1}}{n}\\\dfracn{a_{n-2}}{n}\\
\dfracn{a_1}{n}
y_0 10 \\y_1 1 + 3i \\y_2 8 \\y_31 - 3i
y_0 10 \\y_1 1 + 3i \\y_2 8 \\y_31 - 3i
rollbackEdits.php mass rollback
<tex>
\mathrm{DFT}(a_0, a_1, \ldots , a_{n-1}) = (y_0, y_1, \ldots , y_{n-1}) = (A(\omega_{n,0}), A(\omega_{n,1}), \ldots , A(\omega_{n,n-1}))
</tex>
<tex>
<center>
<tex>
A \times B = \mathrm{InvDFT}(\mathrm{DFT}(A) \times \mathrm{DTFDFT}(B)).
</tex>
</center>
Так как ДПФ многолчена {{---}} это вектор его значений, значит, перемножение двух ДПФ требует только <tex>O(n)</tex> операций. Осталось только вычислять ДПФ и обратное ДПФ за время <tex>O(n \log n)</tex>. Для этого используем [[Быстрое преобразование Фурье| быстрое преобразование Фурье]].
ДПФ также применяют для быстрого умножения двух длинных чисел, которые в свою очередь могут быть представлены в виде полиномов.
== ДПФ в модульной арифметике ==
В основе ДПФ используются комплексные числа, являющиеся корнями <tex>n</tex>-ой степени из единицы. Для эффективного вычисления использовались свойства комплексных корней, которые образуют [[Группа | группу]], то есть степень одного корня всегда является другим корнем. Среди них есть корень, называемый [[Первообразные корни | примитивным]].
Однако, то же верно и в случае корней <tex>n</tex>-ой степени из единицы в модульной арифметике. Не для любого модуля <tex>p</tex> найдется <tex>n</tex> различных корней, но такие модули все же существуют. Необходимо найти примитивный корень, то есть:
== Следствия ==
{{Утверждение
|statement= <tex>\mathrm{DFT}(\mathrm{DFT}(a_0, a_1, \ldots , a_{n-1})) = \dfrac{1}{n} (a_0, a_{n-1}, \ldots , a_1) </tex>
|proof=
Применим к обеим частям обратное ДПФ и получим:
<center>
<tex>
\mathrm{DFT}(a_0, a_1, \ldots , a_{n-1}) = \mathrm{InvDFT}\left(\dfrac{1}{n} (a_0, a_{n-1}, \ldots , a_1)\right)
</tex>
</center>
<center>
<tex>
y_k = \sum\limits_{j=0}^{n-1} a_j e^{i\frac{2\pi k}{n} j}
</tex>
</center>
Теперь рассмотрим правую часть. По определению, справа у нас находится вектор коэффициентов многочлена со значениями <tex>\left( \dfrac{1}{n} a_0, \dfrac{1}{n} a_{n-1}, \ldots , \dfrac{1}{n} a_1 \right)</tex> в точках <tex>x = \omega_n^k</tex>. Обозначим его как <tex>(y_0 ', y_1 ', \ldots , y_{n-1} ')</tex>, где:
<center>
<tex>
y_k '= \dfrac{1}{n} \sum\limits_{j=0}^{n-1} z_j e^{-i\frac{2\pi k}{n} j},
</tex>
</center>
=
\begin{pmatrix}
\vdots \\
\end{pmatrix}
</tex>
<center>
<tex>
y_k ' = a_0 e^0 + \sum\limits_{j=1}^{n-1} a_j e^{-i\frac{2\pi k}{n} (n - j)} = a_0 + \sum\limits_{j=1}^{n-1} a_j e^{-i 2\pi k} e^{i\frac{2\pi k}{n} j}
</tex>
</center>
<center>
<tex>
y_k ' = a_0 + \sum\limits_{j=1}^{n-1} a_j e^{i \frac{2\pi k}{n} j} = \sum\limits_{j=0}^{n-1} a_j e^{i\frac{2\pi k}{n} j} = y_k.
</tex>
</center>
<center>
<tex>
x_0 = \ \ 1 5 \\
x_1 = \ \ 2 \\
x_2 = \ \ 4 \\
1 & i & -1 & -i \\
1 & -1 & 1 & -1 \\
1 & -i & -1 & i
\end{pmatrix}
\begin{pmatrix}
=
\begin{pmatrix}
\end{pmatrix}
</tex>
1 & i & -1 & -i \\
1 & -1 & 1 & -1 \\
1 & -i & -1 & i
\end{pmatrix}}^{-1}
\begin{pmatrix}
\end{pmatrix}
</tex></center>
<center><tex>
\begin{pmatrix}
a_0 \\
a_1 \\
a_2 \\
a_3
\end{pmatrix}
=
\dfrac{1}{-16i}
\begin{pmatrix}
-4i & -4i & -4i & -4i \\
-4i & -4 & 4i & 4 \\
-4i & 4i & -4i & 4i \\
-4i & 4 & 4i & -4
\end{pmatrix}
\begin{pmatrix}
10 \\
1 + 3i \\
8 \\
1 - 3i
\end{pmatrix}
</tex></center>
<center>
<tex>
a_0 = \dfrac{1}{4} (10 + 1 + 3i + 8 + 1 - 3i) = 5 \\
a_1 = \dfrac{1}{4} (10 + (1 + 3i)(-i) + (-1)8 + (1 - 3i)i) = 2 \\
a_2 = \dfrac{1}{4} (10 + (1 + 3i)(-1) + 8 + (1 - 3i)(-1)) = 4 \\
a_3 = \dfrac{1}{4} (10 + (1 + 3i)i + (-1)8 + (1 - 3i)(-i)) = -1
</tex>
</center>
== См. также ==
*[http://e-maxx.ru/algo/fft_multiply MAXimal::algo::Быстрое преобразование Фурье за O (N log N)]
[[Категория: Аналитическая теория Алгоритмы и структуры данных]][[Категория: Алгоритмы алгебры и теории чисел]][[Категория: Основные элементы теории чисел]][[Категория: Основные алгоритмы теории чисел]]
