FFT C++ issue

Hello,
I'm tryung to implement Fast Fourier Transformation. And I'm not sure if I understand it correctly.

As I understand when I transform (for example) simple sine wave by FFT, and than make inversion I should get exactly the same sine wave. Am I right?

But in some way it doesn't work for me. I found that code with the friend google:

Code:

---

#include <complex>
#include <iostream>
#include <valarray>
#include <QVector>
using namespace std;
 
const double PI = 3.141592653589793238460;
 
typedef std::complex<double> Complex;
typedef std::valarray<Complex> CArray;
 
// Cooley–Tukey FFT (in-place, divide-and-conquer)
// Higher memory requirements and redundancy although more intuitive
void fft(CArray& x)
{
    const size_t N = x.size();
    if (N <= 1) return;
 
    // divide
    CArray even = x[std::slice(0, N/2, 2)];
    CArray  odd = x[std::slice(1, N/2, 2)];
 
    // conquer
    fft(even);
    fft(odd);
 
    // combine
    for (size_t k = 0; k < N/2; ++k)
    {
        Complex t = std::polar(1.0, -2 * PI * k / N) * odd[k];
        x[k    ] = even[k] + t;
        x[k+N/2] = even[k] - t;
    }
}
 
// inverse fft (in-place)
void ifft(CArray& x)
{
    // conjugate the complex numbers
    x = x.apply(std::conj);
 
    // forward fft
    fft( x );
 
    // conjugate the complex numbers again
    x = x.apply(std::conj);
 
    // scale the numbers
    x /= x.size();
}
 
int main()
{
    const Complex test[] = { 1.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0 };
    CArray data(test, 8);
 
    // forward fft
    fft(data);
 
    std::cout << "fft" << std::endl;
    for (int i = 0; i < 10; ++i)
    {
        std::cout << data[i] << std::endl;
    }
 
    // inverse fft
    ifft(data);
 
    std::cout << std::endl << "ifft" << std::endl;
    for (int i = 0; i < 10; ++i)
    {
        std::cout << data[i] << std::endl;
    }
    return 0;
}

---

So as I understand by ifft(data) I should receive the same as it was on the beggining, but the results are quite different. Can anyone help me?
For any help thanks in advance.
Best Regards

Hello,

running your program I get the following output (reducing the number of lines to the size of the input data, i.e. 8 instead of 10):

Code:

---

fft
(4,0)
(1,-2.41421)
(0,0)
(1,-0.414214)
(0,0)
(1,0.414214)
(0,0)
(1,2.41421)
 
ifft
(1,-0)
(1,-5.55112e-17)
(1,2.4895e-17)
(1,-5.55112e-17)
(5.55112e-17,0)
(5.55112e-17,5.55112e-17)
(0,-2.4895e-17)
(5.55112e-17,5.55112e-17)

---

Your input was a vector of 4 ones and 4 zeros (real numbers). And that's (up to rounding errors) "exactly" what you get as output of the ifft call: You get a sequence of complex numbers and you should read the x.yze-17 numbers as 0.

Compiled with gcc6.

Best regards
ars

Hello,
thanks for your reply.
Yes you are right. When I try it with the sine wave, with much more sampling points, the iFFT gives me really close results to the input. I think I understand it now.