fastfour.cpp

#include <iostream>
#include <cmath>

using namespace std;

const double PI = 3.141592653589793;

class Complex {
public:
    double real;
    double imag;

    Complex(double r = 0.0, double i = 0.0) {
        real = r;
        imag = i;
    }

    Complex operator + (const Complex& b) const {
        return Complex(real + b.real, imag + b.imag);
    }

    Complex operator - (const Complex& b) const {
        return Complex(real - b.real, imag - b.imag);
    }

    Complex operator * (const Complex& b) const {
        return Complex(real * b.real - imag * b.imag,
                       real * b.imag + imag * b.real);
    }

    void print() {
        cout << real << " + " << imag << "i" << endl;
    }
};

void fft(Complex *a, int n, bool invert) {
    // Bit-reversal permutation
    int j = 0;
    for (int i = 1; i < n; i++) {
        int bit = n >> 1;
        while (j & bit) {
            j ^= bit;
            bit >>= 1;
        }
        j ^= bit;

        if (i < j) {
            Complex temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }

    for (int len = 2; len <= n; len <<= 1) {
        double ang = 2 * PI / len * (invert ? -1 : 1);
        Complex wlen(cos(ang), sin(ang));
        for (int i = 0; i < n; i += len) {
            Complex w(1);
            for (int j = 0; j < len / 2; j++) {
                Complex u = a[i + j];
                Complex v = a[i + j + len / 2] * w;
                a[i + j] = u + v;
                a[i + j + len / 2] = u - v;
                w = w * wlen;
            }
        }
    }

    if (invert) {
        for (int i = 0; i < n; i++) {
            a[i].real /= n;
            a[i].imag /= n;
        }
    }
}

int main() {
    int n;
    cout << "Enter the size of the input (power of 2): ";
    cin >> n;

    Complex *a = new Complex[n];
    cout << "Enter " << n << " real numbers:\n";
    for (int i = 0; i < n; i++) {
        double x;
        cin >> x;
        a[i] = Complex(x, 0);
    }

    fft(a, n, false);

    cout << "\nFFT Result:\n";
    for (int i = 0; i < n; i++) {
        a[i].print();
    }

    // Optional: Inverse FFT to get original back
    fft(a, n, true);
    cout << "\nInverse FFT Result:\n";
    for (int i = 0; i < n; i++) {
        a[i].print();
    }

    delete[] a;
    return 0;
}