Я бился головой об стену на этом DFT. Он должен распечатать: 8,0,0,0,0,0,0,0, но вместо этого я получаю 8, а затем очень и очень маленькие цифры. Это ошибки округления? Что я могу сделать? Мой Radix2 FFT дает правильные результаты, кажется, глупый DFT также не может работать.
Я начал с комплексных чисел, так что я знаю, что ничего хорошего не хватает, я попытался сократить его, чтобы проиллюстрировать проблему.
#include <cstdlib>
#include <math.h>
#include <iostream>
#include <complex>
#include <cassert>
#define SIZE 8
#define M_PI 3.14159265358979323846
void fft(const double src[], double dst[], const unsigned int n)
{
for(int i=0; i < SIZE; i++)
{
const double ph = -(2*M_PI) / n;
const int gid = i;
double res = 0.0f;
for (int k = 0; k < n; k++) {
double t = src[k];
const double val = ph * k * gid;
double cs = cos(val);
double sn = sin(val);
res += ((t * cs) - (t * sn));
int a = 1;
}
dst[i] = res;
std::cout << dst[i] << std::endl;
}
}
int main(void)
{
double array1[SIZE];
double array2[SIZE];
for(int i=0; i < SIZE; i++){
array1[i] = 1;
array2[i] = 0;
}
fft(array1, array2, SIZE);
return 666;
}
Фактически, БПФ может давать более точные результаты, чем прямое вычисление ДПФ, поскольку меньшее количество арифметических операций обычно дает меньше возможностей для накопления ошибок арифметического квантования. Есть статья одного из авторов FFTW на эту тему.
Поскольку DFT / FFT имеют дело с трансцендентальной базисной функцией, результаты никогда не будут (за исключением, возможно, в нескольких особых случаях или по счастливой случайности) быть точными с использованием любого не символьного и конечного формата чисел компьютера. Поэтому значения, очень близкие (в пределах нескольких младших разрядов) к нулю, должны просто игнорироваться как шум или считаться равными нулю.
Других решений пока нет …