Вычислить (x ^ 2 + 1) ^ 3, используя БПФ и ОБПФ

Пока мне удалось запустить БПФ и я получил следующую таблицу коэффициентов:

[2, 1 + i, 0, 1 - i, 2, 1 + i, 0, 1 - i]

Проблема, с которой я сталкиваюсь, состоит в том, чтобы вычислить обратное и получить многочлен в форме коэффициентов. Не могли бы вы помочь мне, объяснив, как определить обратный корень из единицы, который мне нужно использовать? И более широкое объяснение того, как применять IFFT.

Большое спасибо!


algorithm polynomials fft polynomial-math ifft
person Mark    schedule 04.07.2015    source источник
comment
Я не согласен, это алгоритмический вопрос, я прошу объяснить, как сделать алгоритм IFFT, включая некоторые математические моменты, которые я не понял, читая об этом.   -  person Mark    schedule 05.07.2015
comment
Какой язык вы используете? если бы вы смогли выполнить прямое БПФ, тогда выполнение IFFT должно быть легким.   -  person KillaKem    schedule 05.07.2015
comment
На данный момент я пытаюсь решить это только на бумаге, но у меня есть БПФ, написанный на Java.   -  person Mark    schedule 05.07.2015
comment
возможный дубликат БПФ для уравнений, которые имеют члены с разными показателями   -  person Spektre    schedule 06.07.2015

Ответы (1)


arrow_upward
1
arrow_downward

для чего именно вы хотите использовать FFT/IFFT?

  1. если x равно bignum

    • see fast bignum sqr especially Schönhage-Strassen multiplication
    • для ^2 и ^3 вы можете вычислить NTT/FFT только один раз вместо 2 и 3 раз

  2. x^2+1 является полиномиальным

[Примечания]

  • в обоих случаях лучше использовать NTT вместо FFT.
  • из-за потери точности (ошибки округления)
person Spektre    schedule 05.07.2015
comment
Я использую его для умножения многочленов, но вопрос в мелких деталях с корнями из единицы, я не знаю, как их определить. Предоставленная ссылка говорит мне все, что я уже знаю. - person Mark; 06.07.2015
comment
@Отметьте, если вы используете собственный корень из единицы (в конечном поле), то вы выполняете NTT, а не FFT !!! см. ссылку НТТ. не имеет значения, какое простое число по модулю вы выберете, но оно должно быть больше, чем любой из подрезультатов (коэффициентов). Я использую максимальное доступное 32-битное простое число без знака 0xC0000001 Корень единицы и его обратный сложны. Я написал программу, которая ищет все 32-битные числа. диапазон и тест для всех необходимых условий, и результат находится в функции-члене исходного кода ссылки NTT bool fourier_NTT::init(DWORD n) - person Spektre; 06.07.2015
comment
Спасибо! Я посмотрю, и если я не справлюсь, я отпишусь здесь - person Mark; 06.07.2015