FFT и IFFT для умножения полиномов, проблема для нуля ⇐ C++

[Anonymous]

FFT работает правильно, но IFFT, при передаче довольно длинного полинома с коэффициентами 0, возвращает некоторое бессмысленное вместо 0. Вот код: < /p>

Код: Выделить всё

#include 
#include 
#include 

const double PI = 3.14159265358979323846;
typedef unsigned int uint;
typedef std::vector vec;

vec fastFourierTransform(vec& a)
{
uint s = a.size();
if (s == 1) {
return a;
}

vec val(a.size());
for (uint i = 0; i < s; i++) {
std::complexc(cos(2.0 * PI * i / s), sin(2.0 * PI * i / s));
val[i] = c;
}

vec odd(s / 2), nodd(s / 2);
for (uint i = 0; i < s / 2; i++) {
odd[i] = a[i * 2];
nodd[i] = a[i * 2 + 1];
}

vec odref = fastFourierTransform(odd);
vec nodref = fastFourierTransform(nodd);

vec res(s);

for (int k = 0; k < s / 2; k++) {
res[k] = odref[k] + (val[k] * nodref[k]);
res[k + s / 2] = odref[k] - (val[k] * nodref[k]);
}
return res;
}

vec IfastFourierTransform(vec& a)
{
uint s = a.size();
if (s == 1) {
return a;
}

vec val(a.size());
for (uint i = 0; i < s; i++) {
std::complexc(cos(-2.0 * PI * i / s), sin(-2.0 * PI * i / s));
val[i] = c;
}

vec odd(s / 2), nodd(s / 2);
for (uint i = 0; i < s / 2; i++) {
odd[i] = a[i * 2];
nodd[i] = a[i * 2 + 1];
}

vec odref = IfastFourierTransform(odd);
vec nodref = IfastFourierTransform(nodd);

vec res(s);

for (int k = 0; k < s / 2; k++) {
res[k] = odref[k] + (val[k] * nodref[k]);
res[k + s / 2] = odref[k] - (val[k] * nodref[k]);
}
return res;
}

int main()
{
int ammount;
std::cin >> ammount;
std::complex c;
vec V;
double x;
for (uint i = 0; i < ammount; i++) {
std::cin >> x;
std::complexc(x, 0);
V.push_back(c);
}

vec result;
result = fastFourierTransform(V);
std::cout 

Подробнее здесь: [url]https://stackoverflow.com/questions/79578445/fft-and-ifft-for-multiplication-of-polynomials-problem-for-zero[/url]