Cooley-Tukey算法python超出范围

Question

我正在分析用 Python 编写的 Cooley-Tukey 算法实现的复杂性（代码取自here）：

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

该代码与网页中显示的示例配合良好；事实上，它似乎适用于任何长度为 <= 9. For some reason, trying with a list of length > 10:

的列表

print( ' '.join("%5.3f" % abs(f) for f in fft([0,1,2,3,4,5,6,7,8,9])))

返回以下错误：

T = [exp(-2j*pi*k/N)*odd[k] for k in range(N//2)]

IndexError：列表索引超出范围

有谁知道失败的原因吗？

Answer 1

您使用的 Cooley-Tukey 实现假设输入长度是 2 的幂。到目前为止，二的幂输入长度是最容易实现 Cooley-Tukey 的；将此代码扩展到非二次方输入长度需要完全重写它。

Answer 2

这是数字错误，

len(odd)<N//2

。以下代码

try:
    T = [exp(-2j*pi*k/N)*odd[k] for k in range(N//2)]
except IndexError:
    print len(odd), N
    raise

将打印出来

4 10

这意味着当

N==10

、

len(odd)==4

时，你会得到 IndexError。