二位fft的python代码

以下是两个 Python 实现的快速傅里叶变换（FFT）算法：

1. 递归实现：

import cmath

def fft(x):
    n = len(x)
    if n == 1:
        return x
    even = fft(x[0::2])
    odd = fft(x[1::2])
    T = [cmath.exp(-2j * cmath.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)]

2. 非递归实现：

import cmath

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


def fft_iterative(x):
    n = len(x)
    levels = int(n.bit_length()) - 1
    if 2**levels != n:
        raise ValueError("Length is not a power of 2")
    # bit-reversed indices
    rev = [int('{:0{width}b}'.format(i, width=levels)[::-1], 2) for i in range(n)]
    X = x[:]
    # bit-reversed permutation
    for i in range(n):
        if i < rev[i]:
            X[i], X[rev[i]] = X[rev[i]], X[i]
    # Cooley-Tukey decimation-in-time radix-2 FFT
    size = 2
    while size <= n:
        halfsize = size // 2
        tablestep = n // size
        for i in range(0, n, size):
            k = 0
            for j in range(i, i + halfsize):
                t = cmath.exp(-2j * cmath.pi * k / size) * X[j + halfsize]
                X[j + halfsize] = X[j] - t
                X[j] += t
                k += tablestep
        size *= 2
    return X