Дискретное преобразование Фурье — различия между версиями
(→Источники информации) |
(→Применение ДПФ) |
||
(не показано 6 промежуточных версий 4 участников) | |||
Строка 31: | Строка 31: | ||
<center> | <center> | ||
<tex> | <tex> | ||
− | A \times B = \mathrm{InvDFT}(\mathrm{DFT}(A) \times \mathrm{ | + | A \times B = \mathrm{InvDFT}(\mathrm{DFT}(A) \times \mathrm{DFT}(B)). |
</tex> | </tex> | ||
</center> | </center> | ||
Строка 73: | Строка 73: | ||
<center> | <center> | ||
<tex> | <tex> | ||
− | y_k = \sum\limits_{j=0}^{n} a_j e^{i\frac{2\pi k}{n} j} | + | y_k = \sum\limits_{j=0}^{n-1} a_j e^{i\frac{2\pi k}{n} j} |
</tex> | </tex> | ||
</center> | </center> | ||
Строка 81: | Строка 81: | ||
<center> | <center> | ||
<tex> | <tex> | ||
− | y_k '= \dfrac{1}{n} \sum\limits_{j=0}^{n} z_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}, |
</tex> | </tex> | ||
</center> | </center> | ||
Строка 136: | Строка 136: | ||
<center> | <center> | ||
<tex> | <tex> | ||
− | x_0 = \ \ | + | x_0 = \ \ 5 \\ |
x_1 = \ \ 2 \\ | x_1 = \ \ 2 \\ | ||
x_2 = \ \ 4 \\ | x_2 = \ \ 4 \\ | ||
Строка 253: | Строка 253: | ||
*[http://e-maxx.ru/algo/fft_multiply MAXimal::algo::Быстрое преобразование Фурье за O (N log N)] | *[http://e-maxx.ru/algo/fft_multiply MAXimal::algo::Быстрое преобразование Фурье за O (N log N)] | ||
− | [[Категория: | + | [[Категория: Алгоритмы и структуры данных]] |
[[Категория: Алгоритмы алгебры и теории чисел]] | [[Категория: Алгоритмы алгебры и теории чисел]] | ||
+ | [[Категория: Основные элементы теории чисел]] | ||
+ | [[Категория: Основные алгоритмы теории чисел]] |
Версия 18:56, 3 апреля 2019
Определение: |
Дискретное преобразование Фурье (англ. Discrete Fourier Transform, DFT) многочлена где — ый из комплексных корней из единицы. называется главным значением корня -ой степени из единицы, а все остальные корни являются его степенями: . | называют вектор значений этого многочлена в точках :
Определение: |
Обратное дискретное преобразование Фурье (англ. Inverse DFT) для вектора значений многочлена
| — вектор коэффициентов этого многочлена :
Содержание
Применение ДПФ
Дискретное преобразование Фурье используют для быстрого перемножения двух полиномов
и .Для того чтобы получить произведение двух многочленов за время, меньшее чем
, необходимо сначала посчитать обоих многочленов. Так как при умножении двух многочленов их значения просто перемножаются в каждой точке. Следовательно, если — это вектор значений многочлена, то мы можем получить значение произведения двух многочленов, просто перемножив их ДПФ. Значит, чтобы получить коэффициенты полученного многочлена, применим обратное ДПФ.
Так как ДПФ многолчена — это вектор его значений, значит, перемножение двух ДПФ требует только быстрое преобразование Фурье.
операций. Осталось только вычислять ДПФ и обратное ДПФ за время . Для этого используем
ДПФ также применяют для быстрого умножения двух длинных чисел, которые в свою очередь могут быть представлены в виде полиномов.
ДПФ в модульной арифметике
В основе ДПФ используются комплексные числа, являющиеся корнями группу, то есть степень одного корня всегда является другим корнем. Среди них есть корень, называемый примитивным.
-ой степени из единицы. Для эффективного вычисления использовались свойства комплексных корней, которые образуютОднако, то же верно и в случае корней
-ой степени из единицы в модульной арифметике. Не для любого модуля найдется различных корней, но такие модули все же существуют. Необходимо найти примитивный корень, то есть:
Как и с комплексными корнями, остальные
корней -ой степени из единицы по модулю можно получить как степени примитивного корняСледствия
Утверждение: |
Применим к обеим частям обратное ДПФ и получим:
Заметим, что слева у нас находится вектор значений многочлена с коэффициентами и обозначим его за . Заметим, что:
Теперь рассмотрим правую часть. По определению, справа у нас находится вектор коэффициентов многочлена со значениями в точках . Обозначим его как , где:
где
Тогда, подставляя значения , получаем:
А так как , получаем:
|
Пример
Посчитаем
для полинома степени .
Тогда подставляя значения
в получаем:
Построим матрицу Вандермонда:
Получаем вектор значений многочлена
:
В итоге получаем:
Аналогично, получаем обратное ДПФ.