Простейшее битовое преобразование Фурье.

47. битовое преобразование Фурье. перемножить с помощью дискретного битового преобразования Фурье по модулю простого числа (7) (по желанию Можно взять больший простой модуль, например 11,17 и т.д.). два числа cиd. если их произведение оказывается больше 63. одно из них разделить пополам, взять целую часть. желательно, чтобы при этом не получилось число 5 - чтобы этого избежать поделите другое число (ибо пример с числом 5 разобран нами ниже).

обратная матрицаили , что тоже, потому что.

пример перемножим число 5 и 5 (у нас слишком мало примеров ограниченной сложности, поэтому не будем показывать два разных числа)

, второе число совпадает с первым поэтому результат тот же

=

Восстановим результат перемножения полиномов с помощью поразрядного сдвига

.

Теория. Преобразование Фурье.

, где - примитивный кореньn+1 степени из 1. Обычно корни бывают в комплексной плоскости вида над полем комплексных чисел, - обычно берётся кореньn+1 степени из 1:(для удобства проведения быстрого преобразования Фурье важно, чтобы,), либо корни по модулю натурального числа. здесь тоже бывает важно, чтобы это был корень степени.

пример .

идея основана на

тогда вычисление прямого преобразования Фурье есть вычисление полинома в точках

1, ,,,..,,.

с учетом равенства

вычисление обратного преобразования Фурье основано на вычислении полинома с коэффициентами полученными на предыдущем этапе в точках обратным предыдущим

1, ,,,..,,.

и делении итогового результата на число точек.

Пример

Уточним корни

прямое преобразование ,обратное преобразование

проверим, что данные преобразования и их матрицы при перемножении дают единичную матрицу

.

Задача. Вычислить по схеме Горнера полином , вычислить в точкаx=1, х=-1,x=2,x=i, х=-i

общий подход

Теория Быстрого преобразования Фурье - продолжение предыдущего раздела:

Вычисления преобразования Фурье с помощью схемы Горнера во всех точках займет n²действий, что много и представляет проблему если вектор большой. при частоте 48 килогерц принятой при аудиозаписи в час мы имеемn=50 000c^-1*4000c=200 000 000 компонент (читатель привыкший считать независимо от обстоятельств точно, наверное убеждён в НАШЕМ часе 60*60=3600 секунд, что примерно 4000). квадрат этого числа 4 10¹⁶

Быстрое преобразование Фурье позволяет вычислить за , что как минимум в миллион раз быстрее. Быстрое преобразование Фурье делается на корнях степении интегрирует идеи быстрого возведения в степень и схемы Горнера быстрого вычисления полиномов в одной точке.

Всё основано на равенстве.

. Мы последовательно разлагаем полином на четный и нечетный. из нечетного полинома выносимx, в результате имеем два полинома от