Изменения
→Применение ДПФ
<center>
<tex>
A \times B = \mathrm{InvDFT}(\mathrm{DFT}(A) \times \mathrm{DTFDFT}(B)).
</tex>
</center>
<center>
<tex>
y_k = \sum\limits_{j=0}^{n-1} a_j e^{i\frac{2\pi k}{n} j}
</tex>
</center>
<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>
<center>
<tex>
x_0 = \ \ 1 5 \\
x_1 = \ \ 2 \\
x_2 = \ \ 4 \\
*[http://e-maxx.ru/algo/fft_multiply MAXimal::algo::Быстрое преобразование Фурье за O (N log N)]
[[Категория: Дискретная математика Алгоритмы и алгоритмыструктуры данных]][[Категория: Алгоритмы алгебры и теории чисел]][[Категория: Основные элементы теории чисел]][[Категория: Аналитическая теория Основные алгоритмы теории чисел]]
