frequency analysis without numpy

sturlamolden sturlamolden at
Wed Jan 21 12:31:26 CET 2009

On Jan 21, 12:13 am, sturlamolden <sturlamol... at> wrote:

> Apart from that, an FFT in pure python is going to be atrociously slow
> for anything but the shortest signals. I cannot imagine why you want
> to do this.

Just to elaborate on this:

The whole purpose of using FFT is speed. That pretty much excludes the
use of Python.

If you don't care about speed, you could just as well compute the DFT
directly. The FFT is just a O(n lon n) algorithm for computing the
DFT. Here is a DFT with O(N**2) behavior:

from math import sin, cos, pi

def real_dft(x):
   ''' DFT for a real valued sequence x '''
   r = []
   N = len(x)
   M = N//2 + 1 if N%2 else N//2
   for n in range(M):
      s = 0j
      for k in range(N):
         tmp = 2*pi*k*n/N
         s += x[k] * (cos(tmp) - 1j*sin(tmp))
   return r


More information about the Python-list mailing list