Общий случай

Общий случай может быть сведён к предыдущему. Пусть . Заметим, что . Обозначим . Тогда , если положить при .

Таким образом задача сведена к вычислению свёртки, но это можно сделать с помощью трёх преобразований Фурье для 2^k элементов. Выполняем прямое преобразование Фурье для и , перемножаем поэлементно результаты и выполняем обратное преобразование Фурье.

Вычисления всех и c_i требуют O(N) действий, три преобразования Фурье требуют O(Nlog(N)) действий, перемножение результатов преобразований Фурье требует O(N)действий, вычисление всех b_i зная значения свертки требует O(N) действий. Итого для дискретного преобразования Фурье требуется O(Nlog(N)) действий для любого N.

Этот алгоритм быстрого преобразования Фурье может работать над кольцом только когда известны первообразные корни из единицы степеней 2N и 2^k.

Вывод преобразования из ДПФ

Дискретное преобразование Фурье для вектора , состоящего из N элементов, имеет вид:

элементы матрицы имеют вид: .

Пусть N четно, тогда ДПФ можно переписать следующим образом:

Коэффициенты и можно переписать следующим образом (M=N/2):

В результате получаем:

То есть дискретное преобразование Фурье от вектора, состоящего из N отсчетов, свелось к линейной композиции двух ДПФ от отсчетов, и если для первоначальной задачи требовалось N² операций, то для полученной композиции — . Если M является степенью двух, то это разделение можно продолжать рекурсивно до тех пор, пока не дойдем до двухточечного преобразования Фурье, которое вычисляется по следующим формулам: