Anonymous user
Fast Fourier transform: Difference between revisions
→{{header|Python}}
No edit summary |
|||
Line 64:
=={{header|Python}}==
<lang python>from cmath import exp, pi
def fft(x):
N = len(x)
if N <= 1: return x
even = fft(x[0::2])
odd = fft(x[1::2])
return [even[k] + exp(-2j*pi*k/N)*odd[k] for k in xrange(N/2)] + \
[even[k] - exp(-2j*pi*k/N)*odd[k] for k in xrange(N/2)]
print fft([1.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0])</lang>
Output:
<pre>[(4+0j), (1-2.4142135623730949j), 0j, (1-0.41421356237309492j), 0j, (0.99999999999999989+0.41421356237309492j), 0j, (0.99999999999999967+2.4142135623730949j)]</pre>
Using module [http://numpy.scipy.org/ numpy].
<lang python>>>> from numpy.fft import fft
| |||