frequency analysis without numpy

[sturlamolden]

On Jan 21, 12:13 am, sturlamolden <sturlamol... at yahoo.no> 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))
      r.append(s)
   return r



S.M.