Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <complex>
- #include <iostream>
- #include <valarray>
- const double PI = 3.141592653589793238460;
- typedef std::complex<double> Complex;
- typedef std::valarray<Complex> CArray;
- 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;
- }
- }
- 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 < 8; ++i)
- {
- std::cout << data[i] << std::endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement