c++ 实现快速傅里叶变换

快速傅里叶变换（FFT）是一种高效的算法，用于计算离散傅里叶变换（DFT）。它在信号处理、图像处理、声音处理等领域被广泛应用。以下是一个简单的 C 语言实现 FFT 的示例代码：

#include <stdio.h>
#include <math.h>

#define PI 3.14159265358979323846

void fft(double *real, double *imag, int n) {
    if (n <= 1) return;
    double even_real[n/2], even_imag[n/2];
    double odd_real[n/2], odd_imag[n/2];
    for (int i = 0; i < n/2; i++) {
        even_real[i] = real[2*i];
        even_imag[i] = imag[2*i];
        odd_real[i] = real[2*i+1];
        odd_imag[i] = imag[2*i+1];
    }
    fft(even_real, even_imag, n/2);
    fft(odd_real, odd_imag, n/2);
    for (int k = 0; k < n/2; k++) {
        double t_real = even_real[k];
        double t_imag = even_imag[k];
        double angle = -2 * PI * k / n;
        double w_real = cos(angle);
        double w_imag = sin(angle);
        real[k] = t_real + w_real * odd_real[k] - w_imag * odd_imag[k];
        imag[k] = t_imag + w_real * odd_imag[k] + w_imag * odd_real[k];
        real[k+n/2] = t_real - w_real * odd_real[k] + w_imag * odd_imag[k];
        imag[k+n/2] = t_imag - w_real * odd_imag[k] - w_imag * odd_real[k];
    }
}

int main() {
    double real[] = {1, 0, 1, 0, 1, 0, 1, 0};
    double imag[] = {0, 0, 0, 0, 0, 0, 0, 0};
    int n = sizeof(real) / sizeof(double);
    fft(real, imag, n);
    for (int i = 0; i < n; i++) {
        printf("%f + %fi\n", real[i], imag[i]);
    }
    return 0;
}

该代码实现了一个简单的 FFT 算法，可以接受实数和虚数数组作为输入，并计算它们的傅里叶变换。在主函数中，我们将一个长度为8的实数数组传递给 FFT 函数，并打印出计算得到的结果。

需要注意的是，该代码只是一个简单的示例，可能无法处理大规模的数据集。对于实际应用中的数据处理，需要使用更高效的算法和数据结构，以提高计算效率和准确性。