庫利 - 圖基算法蟒蛇超出範圍

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;將此代碼擴展到非冪次冪輸入長度需要完全重寫它。