A simple FFT in Python
Posted Tuesday, October 9th, 2007 at 6:57 pm
I wrote this to check my pen-and-paper FFT (Fast Finite Fourier) problems for my Algorithms and Data homework. It follows a pseudocode implementation given in my textbook, from which I have no idea where it was derived from.
#!/sw/bin/python
i = complex(0,1)
ni = complex(0,-1)
def fft(a,w):
if (w==1):
return a
s = fft([a[z] for z in range(0,len(a),2)], w**2)
sp = fft([a[z] for z in range(1,len(a),2)], w**2)
n = len(a)
r=[]
for j in range(0,(n/2)):
r.insert(j, (s[j] + (w**j * sp[j])))
r.insert(j+(n/2), s[j] - (w**j * sp[j]))
return r
def mult(poly1, poly2):
a= len(poly1)
b= len(poly2)
if a > b:
for x in range(0, a-b):
poly2.append(0)
if b > a:
for x in range(0, b-a):
poly1.append(0)
fftval1 = fft(poly1,i)
fftval2 = fft(poly2,i)
multip = [fftval1[x]*fftval2[x] for x in range(0,len(fftval1))]
inverse = [ (1.0/(len(multip))*x).real for x in fft(multip,ni)]
return inverse
#test
assert mult([1,1,2,0], [2,3,0,0]) == [2,5,7,6]
Apparently there is a fully featured FFT library in scipy, so really I am just happy to have something on my own that works for my needs.
This post is filed under Computer Science. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.