2013-04-10 21:29:02 -07:00
|
|
|
from cmath import exp, pi
|
|
|
|
|
|
|
|
|
|
def fft(x):
|
|
|
|
|
N = len(x)
|
|
|
|
|
if N <= 1: return x
|
2015-11-18 06:14:39 +00:00
|
|
|
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)]
|
2013-04-10 21:29:02 -07:00
|
|
|
|
2015-02-20 00:35:01 -05:00
|
|
|
print( ' '.join("%5.3f" % abs(f)
|
|
|
|
|
for f in fft([1.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0])) )
|
