库利 - 图基算法蟒蛇超出范围

Question

我分析的库利 - 图基算法的实现，用Python编写的复杂度（代码从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。出于某种原因，任何列表进行工作，> 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: list index out of range

不谁知道这个失败的原因？

Answer 1

这是数字错误，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。

Answer 2

您使用的Cooley-Tukey实现假定输入长度是2的乘方。两路输入长度是迄今为止最容易实现的Cooley-Tukey;将此代码扩展到非幂次幂输入长度需要完全重写它。