Cooley-Tukey-Algorithmus Python außerhalb des Bereichs

Question

ich die Komplexität einer Implementierung des Cooley-Tukey-Algorithmus bin Analyse, in Python geschrieben (der Code von here genommen wurde):

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)] 

Der Code funktioniert gut mit das Beispiel auf der Webseite; in der Tat, es scheint, mit einer Liste mit einer Länge < = 9. Aus irgendeinem Grund versucht, mit einer Liste der Länge> 10 zu arbeiten:

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

gibt die folgende Fehlermeldung:

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

IndexError: list index out of range

Does Wer weiß, warum das scheitert?

Answer 1

Dies ist ein numerischer Fehler, len(odd)<N//2. Der folgende Code

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

wird druckt

4 10 

was bedeutet, wenn N==10, len(odd)==4 so bekam man Indexerror.

Answer 2

Die von Ihnen verwendete Cooley-Tukey-Implementierung setzt voraus, dass die Eingangslänge eine Zweierpotenz ist. Power-of-Two-Eingangslängen sind bei weitem am einfachsten zu implementieren Cooley-Tukey für; Eine Erweiterung dieses Codes auf Nicht-Zweier-Eingangslängen würde ein vollständiges Neuschreiben erfordern.