9 import threading, Queue
12 class Thread(threading.Thread):
13 def __init__(self,x, inverse=False, spawn_threads=1):
14 threading.Thread.__init__(self)
16 self.inverse = inverse
18 self.spawn_threads = spawn_threads
21 #print "Thread " + str(threading.current_thread()) + " runs\n"
22 self.X = fft(self.x, self.inverse, self.spawn_threads)
25 def dft(x, inverse = False):
27 #print "Using Brute Force"
30 inv = -1 if not inverse else 1
35 X[k] += x[n] * cmath.exp(inv * 2.0j * cmath.pi * float(k * n) / float(N))
41 def fft(x, inverse = False, spawn_threads=1):
48 inv = -1 if not inverse else 1
51 return dft(x, inverse)
53 #print "Active threads " + str(threading.active_count()) + "; in thread " + str(threading.current_thread())
54 if threading.active_count() < spawn_threads:
55 threads = [Thread(x[0::2]), Thread(x[1::2])]
63 X = threads[0].X + threads[1].X
65 X = fft(x[0::2]) + fft(x[1::2])
68 for k in range(0, N/2):
70 X[k] = t + cmath.exp(inv * 2.0j * cmath.pi * float(k) / float(N)) * X[k + (N/2)]
71 X[k+(N/2)] = t - cmath.exp(inv * 2.0j * cmath.pi * float(k) / float(N)) * X[k + (N/2)]
76 return map(lambda j : j / 2.0, X)
78 def transpose(lists, defval=0.0):
79 if not lists: return []
80 return map(lambda *row : [elem or defval for elem in row], *lists)
86 def fft2d(x, inverse = False):
89 for k in range(0, len(xt)):
90 temp[k] = fft(xt[k], inverse)
92 temp = transpose(temp)
94 for k in range(0, len(temp)):
95 X[k] = fft(temp[k], inverse)
100 for i in range(0, len(x)/2):
101 for j in range(0, len(x[i])/2):
103 x[i][j] = x[i+len(x)/2][j+len(x[i])/2]
104 x[i+len(x)/2][j+len(x[i])/2] = t
106 for i in range(len(x)/2, len(x)):
107 for j in range(0, len(x[i])/2):
109 x[i][j] = x[i-len(x)/2][j+len(x[i])/2]
110 x[i-len(x)/2][j+len(x[i])/2] = t
118 if __name__ == "__main__":
119 sys.exit(main(sys.argv))