fft.py

import math

def fft(n, data):
  theta = math.pi * 2 / n

  def scramble(k, i):
    while True:
      i ^= k
      if i >= k:
        return i
      k >>= 1

  i = 0
  for j in range(1, n - 1):
    i = scramble(n >> 1, i)
    if j < i:
      (data[i], data[j]) = (data[j], data[i])

  mh = 1
  while True:
    m = mh << 1
    if m > n:
      break

    irev = 0
    for i in range(0, n, m):
      w = math.cos(theta * irev) + math.sin(theta * irev) * 1j
      irev = scramble(n >> 2, irev)
      for j in range(i, i + mh):
	k = j + mh
	(data[j], data[k]) = (data[j] + data[k], (data[j] - data[k]) * w)

    mh = m

if __name__ == '__main__':
  n = 32

  th = math.pi * 2 / n
  data = [math.sin(th * i) for i in range(0, n)]
  print '# input'
  for i in range(0, n):
    print data[i]

  fft(n, data)

  print
  print '# result'
  for i in range(0, n):
    print '%10.6f' % abs(data[i])