FFT

#include <iostream>

#include <cmath>

#include <complex>

using namespace std;

// Define complex type for convenience

typedef complex<double> Complex;

// Recursive FFT implementation

void recursiveFFT(Complex a[], int n, Complex y[]) {

    // Base case: if n = 1, return a

    if (n == 1) {

        y[0] = a[0];

        return;

    }

    // Calculate principal complex nth root of unity

    Complex wn = exp(Complex(0, 2 * M_PI / n));

    Complex w = 1;

    // Split the input coefficients into even and odd indices

    Complex A0[n / 2], A1[n / 2];

    for (int i = 0; i < n; i += 2) {

        A0[i / 2] = a[i];

        A1[i / 2] = a[i + 1];

    }

    // Compute FFT recursively for even and odd parts

    Complex y0[n / 2], y1[n / 2];

    recursiveFFT(A0, n / 2, y0);

    recursiveFFT(A1, n / 2, y1);

    // Compute FFT for the entire polynomial

    for (int k = 0; k < n / 2; ++k) {

        y[k] = y0[k] + w * y1[k];

        y[k + n / 2] = y0[k] - w * y1[k];

        w *= wn;

    }

}

int main() {

    // Input coefficients of the polynomial

    Complex a[] = {1, 2, 3, 4};

    int n = sizeof(a) / sizeof(a[0]);

    // Result array to store FFT coefficients

    Complex fft_result[n];

    // Compute FFT

    recursiveFFT(a, n, fft_result);

    // Print the FFT result

    cout << "FFT result:" << endl;

    for (int i = 0; i < n; ++i) {

        cout << fft_result[i] << " ";

    }

    cout << endl;

    return 0;

}