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.
