Как на самом деле реализовать полиномиальное умножение с использованием БПФ?
Я изучал эту тему в учебнике по алгоритмам.
Умное использование сложных корней единства, похоже, математически работает. Однако я не понимаю, как можно на самом деле представить это на компьютере.
Я могу думать о двух вещах:
- Используйте вещественное / мнимое разложение для представления комплексных чисел. Но это означает использование чисел с плавающей точкой, что означает, что я открываю свой алгоритм для числовой ошибки, и я теряю точность, даже если я хочу умножить два полинома на целые коэффициенты.
- Представьте exp (i 2pi / n) как n. Таким образом, я в конечном итоге получу кортеж в омеге, и если мне придется сохранить его в этой форме, я по сути снова буду делать полиномиальное умножение в омеге, возвращая нас к исходной точке.
Мне бы очень хотелось увидеть реализацию этого алгоритма на знакомом языке программирования.
1 ответ
На самом деле, как вы выяснили, корни единства обычно не являются хорошими числами, которые можно хорошо хранить в компьютере. Поскольку числовая ошибка мала, если вы знаете, что выходные данные должны быть целыми числами, округление обычно дает правильный результат.
Если вы не хотите (или не можете) полагаться на это, точным вариантом является Теоретическое преобразование числа. Он заменяет корни единицы на комплексной плоскости корнями единицы в конечном поле ℤ/pℤ, где p - подходящее простое число. р должен быть достаточно большим, чтобы существовали все необходимые корни, а эффективность зависит от свойств р. Если вы выберете простое число Ферма, тогда корни единицы имеют удобные формы, и есть хитрость, чтобы сделать редукцию по модулю p более эффективно, чем обычно. Это все точная целочисленная арифметика, и значения остаются небольшими, поэтому нет проблем с ее реализацией на компьютере.
Этот метод используется в алгоритме Шёнхаге-Штрассена, поэтому вы можете посмотреть его особенности.