Проблемы с использованием БПФ при умножении больших чисел

Я недавно пытался умножить кучу (до 10 ^ 5) очень маленьких чисел (порядка 10 ^ -4) друг на друга, поэтому я бы закончил в порядке 10 ^ — (4 * 10 ^ 5), что не вписывается ни в одну переменную.

Мой подход заключается в следующем:

1. Умножьте каждое число на 10 ^ 8 и сохраните его в массиве, разделенном на степени 10, т. Е. Я делаю из него полином, определяемый степенями 10. Примером может быть: p = 0,1234 -> p * 10 ^ 8 = 12340000 -> A = {0, 0, 0, 0, 4, 3, 2, 1}.
2. Умножьте эти массивы, используя FFT
3. если результат

Это делается несколько раз для небольшого количества разных случаев.
В конце я хочу знать, какова доля одного такого продукта над суммой всех продуктов с точностью до 10 ^ -6. Для этого между шагами 2 и 3 результат добавляется в массив сумм, который в конце также iFFTed. Поскольку требуемая точность довольно низкая, я не делю многочлены, а принимаю только первые несколько чисел в целое число.

Моя проблема заключается в следующем: БПФ и / или iFFT не работает должным образом! Я новичок в этом деле и только один раз реализовал БПФ. Мой код выглядит следующим образом (C ++ 14):

#include <cstdio>
#include <vector>
#include <cmath>
#include <complex>
#include <iostream>
using namespace std;

const double PI = 4*atan(1.0);

vector<complex<double>> FFT (vector<complex<double>> A, long N)
{
vector<complex<double>> Ans(0);
if(N==1)
{
Ans.push_back(A[0]);
return Ans;
}
vector<complex<double>> even(N/2);
vector<complex<double>> odd(N/2);
for(long i=0; i<(N/2); i++)
{
even[i] = A[2*i];
odd[i] = A[2*i+1];
}
vector<complex<double>> L1 = FFT(even, N/2);
vector<complex<double>> L2 = FFT(odd, N/2);
for(long i=0; i<N; i++)
{
complex<double> z(cos(2*PI*i/N),sin(2*PI*i/N));
long k = i%(N/2);
Ans.push_back(L1[k] + z*L2[k]);
}
return Ans;
}

vector<complex<double>> iFFT (vector<complex<double>> A, long N)
{
vector<complex<double>> Ans(0);
if(N==1)
{
Ans.push_back(A[0]);
return Ans;
}
vector<complex<double>> even(N/2);
vector<complex<double>> odd(N/2);
for(long i=0; i<(N/2); i++)
{
even[i] = A[2*i];
odd[i] = A[2*i+1];
}
vector<complex<double>> L1 = FFT(even, N/2);
vector<complex<double>> L2 = FFT(odd, N/2);
for(long i=0; i<N; i++)
{
complex<double> z(cos(-2*PI*i/N),sin(-2*PI*i/N));
complex<double> inv(double(1.0/N), 0);
long k = i%(N/2);
Ans.push_back(inv*(L1[k]+z*L2[k]));
}
return Ans;
}

vector<complex<double>> PMult (vector<complex<double>> A, vector<complex<double>> B, long L)
{
vector<complex<double>> Ans(L);
for(int i=0; i<L; i++)
{
Ans[i] = A[i]*B[i];
}
return Ans;
}

vector<complex<double>> DtoA (double x)
{
vector<complex<double>> ans(8);
long X = long(x*10000000);
ans[0] = complex<double>(double(X%10), 0.0); X/=10;
ans[1] = complex<double>(double(X%10), 0.0); X/=10;
ans[2] = complex<double>(double(X%10), 0.0); X/=10;
ans[3] = complex<double>(double(X%10), 0.0); X/=10;
ans[4] = complex<double>(double(X%10), 0.0); X/=10;
ans[5] = complex<double>(double(X%10), 0.0); X/=10;
ans[6] = complex<double>(double(X%10), 0.0); X/=10;
ans[7] = complex<double>(double(X%10), 0.0);
return ans;
}

int main()
{
vector<vector<complex<double>>> W;
int T, N, M;
double p;
scanf("%d", &T);
while( T-- )
{
scanf("%d %d", &N, &M);
W.resize(N);
for(int i=0; i<N; i++)
{
cin >> p;
W[i] = FFT(DtoA(p),8);
for(int j=1; j<M; j++)
{
cin >> p;
W[i] = PMult(W[i], FFT(DtoA(p),8), 8);
}
}
vector<complex<double>> Sum(8);
for(int j=0; j<8; j++) Sum[j]=W[0][j];
for(int i=1; i<N; i++)
{
for(int j=0; j<8; j++)
{
Sum[j]+=W[i][j];
}
}

W[0]=iFFT(W[0],8);
Sum=iFFT(Sum, 8);

long X=0;
long Y=0;
int a;
for(a=0; Sum[a].real()!=0; a++);
for(int i=a; i<8; i++)
{
Y*=10;
Y=Y+long(Sum[i].real());
}
for(int i=a; i<8; i++)
{
X*=10;
X=X+long(W[0][i].real());
}
double ans = 0.0;
if(Y) ans=double(X)/double(Y);
printf("%.7f\n", ans);
}
}

Я заметил, что для массива, который состоит только из нулей, кроме одной записи, FFT возвращает массив с более чем одной непустой записью. Кроме того, после того, как iFFT сделан, результат все еще содержит записи с ненулевой мнимой частью.

Может кто-нибудь найти ошибку или дать мне совет, где я мог бы упростить решение? Поскольку я хочу, чтобы это было быстро, я не хотел бы делать наивное умножение. Будет ли алгоритм Карацубы лучше, так как мне не нужны комплексные числа?