用不同的语言实现快速傅立叶变换

快速傅立叶变换（FFT）是一种高效的算法，用于计算离散傅立叶变换。下面是使用几种不同的编程语言实现FFT的示例代码：

Python:

import numpy as np

def fft(x):
    N = len(x)
    if N <= 1:
        return x
    even = fft(x[0::2])
    odd = fft(x[1::2])
    T = [np.exp(-2j * np.pi * k / N) * odd[k] for k in range(N // 2)]
    return [even[k] + T[k] for k in range(N // 2)] + [even[k] - T[k] for k in range(N // 2)]

# Example usage:
x = [0, 1, 2, 3, 4, 5, 6, 7]
X = fft(x)
print(X)

C++:

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

const double PI = 3.141592653589793238460;

typedef std::complex<double> Complex;
typedef std::valarray<Complex> ComplexArray;

void fft(ComplexArray& x) {
    const size_t N = x.size();
    if (N <= 1) return;

    ComplexArray even = x[std::slice(0, N/2, 2)];
    ComplexArray odd = x[std::slice(1, N/2, 2)];

    fft(even);
    fft(odd);

    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() {
    ComplexArray x = {0, 1, 2, 3, 4, 5, 6, 7};
    fft(x);

    for (const auto& val : x) {
        std::cout << val << std::endl;
    }

    return 0;
}

Java:

import org.apache.commons.math3.complex.Complex;

public class FFT {

    public static Complex[] fft(Complex[] x) {
        int N = x.length;
        if (N <= 1) return x;

        Complex[] even = new Complex[N/2];
        Complex[] odd = new Complex[N/2];
        for (int i = 0; i < N/2; i++) {
            even[i] = x[2*i];
            odd[i] = x[2*i + 1];
        }

        Complex[] evenResult = fft(even);
        Complex[] oddResult = fft(odd);

        Complex[] result = new Complex[N];
        for (int k = 0; k < N/2; k++) {
            double kth = -2 * k * Math.PI / N;
            Complex t = oddResult[k].multiply(new Complex(Math.cos(kth), Math.sin(kth)));
            result[k] = evenResult[k].add(t);
            result[k + N/2] = evenResult[k].subtract(t);
        }
        return result;
    }

    public static void main(String[] args) {
        Complex[] x = {new Complex(0, 0), new Complex(1, 0), new Complex(2, 0), new Complex(3, 0),
                       new Complex(4, 0), new Complex(5, 0), new Complex(6, 0), new Complex(7, 0)};
        Complex[] X = fft(x);

        for (Complex val : X) {
            System.out.println(val);
        }
    }
}

这些示例代码只是FFT的基本实现，实际使用时可能需要根据具体需求进行修改和优化