Изменения

\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}))

A \times B = \mathrm{InvDFT}(\mathrm{DFT}(A) \times \mathrm{DTFDFT}(B)).

Так как ДПФ многолчена {{---}} это вектор его значений, значит, перемножение двух ДПФ требует только <tex>O(n)</tex> операций. Осталось только вычислять ДПФ и обратное ДПФ за время <tex>O(nlognn \log n)</tex>. Для этого используем [[Быстрое преобразование Фурье| быстрое преобразование Фурье]].  ДПФ также применяют для быстрого умножения двух длинных чисел, которые в свою очередь могут быть представлены в виде полиномов.

В основе ДПФ используются комплексные числа, являющиеся корнями <tex>n</tex>-ой степени из единицы. Для эффективного вычисления использовались свойства комплексных корней, которые образуют [[Группа | группу]], то есть степень одного корня всегда является другим корнем. Среди них есть корень, называемый [[Первообразные корни | примитивным]].

y_k = \sum\limits_{j=0}^{n-1} a_j e^{i\frac{2\pi k}{n} j}

y_k '= \dfrac{1}{n} \sum\limits_{j=0}^{n-1} z_j e^{-i\frac{2\pi k}{n} j},

y_k ' = a_0 + \sum\limits_{j=1}^{n} a_j e^{i \frac{2\pi k}{n} j} = \sum\limits_{j=0}^{n} a_j e^{i\frac{2\pi k}{n} j} = y_k,.

x_0 = \ \ 1 5 \\

y_0 10 \\y_1 1 + 3i \\y_2 8 \\y_31 - 3i

\mathrm{DFT}(A) = (10, 1 + 3i, 8, 1 - 3i)</tex></center> Аналогично, получаем обратное ДПФ. <center><tex>\begin{pmatrix}a_0 \\a_1 \\a_2 \\a_3\end{pmatrix}={\begin{pmatrix}1 & 1 & 1 & 1 \\1 & i & -1 & -i \\1 & -1 & 1 & -1 \\1 & -i & -1 & i\end{pmatrix}}^{-1}\begin{pmatrix}10 \\1 + 3i \\8 \\1 - 3i\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

[[Категория: Аналитическая теория Алгоритмы и структуры данных]][[Категория: Алгоритмы алгебры и теории чисел]][[Категория: Основные элементы теории чисел]][[Категория: Основные алгоритмы теории чисел]]