c++ fft

#include <iostream>
#include <complex>
#include <valarray>
#include <cmath>

const double PI = 3.141592653589793238460;

// 函数用于计算FFT
void fft(std::valarray<std::complex<double>> &a) {
    int n = a.size();
    if (n <= 1) return;

    // 分离偶数和奇数索引的元素
    std::valarray<std::complex<double>> even = a[std::slice(0, n/2, 2)];
    std::valarray<std::complex<double>> odd = a[std::slice(1, n/2, 2)];

    // 递归调用FFT
    fft(even);
    fft(odd);

    for (int k = 0; k < n/2; ++k) {
        std::complex<double> t = std::polar(1.0, -2 * PI * k / n) * odd[k];
        a[k] = even[k] + t;
        a[k + n/2] = even[k] - t;
    }
}

int main() {
    // 输入序列
    std::valarray<std::complex<double>> a = {
        {0, 0}, {1, 0}, {2, 0}, {3, 0},
        {4, 0}, {5, 0}, {6, 0}, {7, 0}
    };

    // 计算FFT
    fft(a);

    // 输出结果
    for (std::complex<double> c : a) {
        std::cout << c << '\n';
    }

    return 0;
}

解释说明

1. 包含头文件:

   • #include <iostream>: 用于输入输出。
   • #include <complex>: 支持复数运算。
   • #include <valarray>: 提供数值数组的支持。
   • #include <cmath>: 提供数学函数，如 polar 和 sin/cos。

2. 定义常量:

   • const double PI: 定义圆周率。

3. FFT 函数:

   • void fft(std::valarray<std::complex<double>> &a): 实现快速傅里叶变换（FFT）。
   • 如果数组长度小于等于1，直接返回。
   • 将数组分为偶数和奇数索引的子数组，并递归调用 fft。
   • 使用旋转因子 std::polar(1.0, -2 * PI * k / n) 进行蝶形运算，更新原数组。

4. 主函数:

   • 创建一个复数数组 a，表示输入序列。
   • 调用 fft(a) 计算 FFT。
   • 输出 FFT 结果。

这段代码展示了如何使用 C++ 实现一个简单的 FFT 算法，并对一个给定的输入序列进行变换。