# unencountered error in FFT python

uche uraniumore238 at gmail.com
Sat Jan 30 19:33:42 CET 2010

Hi,
I have the following FFT python code and it doesn't seem to compile
correctly. To run it, please create a file called output.csv with
1,2,3,4,5,6,7,8. simply run the main function. I get an error such as
the following:

x[a], x[b] = x[(a)] + W[(n % N)] * x[(b)], x[(a)] - W[(n % N)] * x
[(b)]
TypeError: list indices must be integers, not float

How can I fixe this problem ? I have tried puttin int on all of the
variables, but I don't think that is the intension of the person who
wore the original code.

#!/usr/bin/python
"""
FFT using Cooley-Tukey algorithm where N = 2^n.  The choice of
e^{-j2\pi/N} or e^{j2\pi/N} is made by 'sign=-1' or 'sign=1'
respectively.  Since I prefer Engineering convention, I chose
'sign=-1' as the default.

FFT is performed as follows:
1. bit-reverse the array.
2. partition the data into group of m = 2, 4, 8, ..., N data points.
3. for each group with m data points,
1. divide into upper half (section A) and lower half (section B),
each containing m/2 data points.
2. divide unit circle by m.
3. apply "butterfly" operation
|a| = |1  w||a|	or	a, b = a+w*b, a-w*b
|b|   |1 -w||b|
where a and b are data points of section A and B starting from
the top of each section, and w is data points along the unit
circle starting from z = 1+0j.
FFT ends after applying "butterfly" operation on the entire data array
as whole, when m = N.
"""

def main():

array = []
array2 = []

import os
import time

os.path.exists("input.csv")

fin=open('input.csv', 'r')

for line in fin:    #read the line from the file

array=line.split(',')

for a in range(len(array)): #convert into integers

array2.append((array[a]))

Ti=time.time()
print (fft(array2))
Tf=time.time()
print (("It took"),Tf-Ti,("seconds to calculate an FFT of
size"),len(array))
#end timer

"""
Find 2^n that is equal to or greater than.
"""

def nextpow2(i):
n = 2
while n < i: n = n * 2
return n

"""
Return bit-reversed list, whose length is assumed to be 2^n:
eg. 0111 <--> 1110 for N=2^4.
"""
def bitrev(x):

N, x = len(x), x[:]
if N != nextpow2(N): raise ValueError ('N is not power of 2')
for i in range(N):
k, b, a = 0, N>>1, 1
while b >= a:
if b & i: k = k | a
if a & i: k = k | b
b, a = b>>1, a<<1
if i < k: x[i], x[k] = (x[k],x[i])
return x

def fft(x, sign=-1):
from cmath import pi, exp
N, W = len(x), []
for i in range(N):		# exp(-j...) is default
W.append(exp(sign * 2j * pi * i / N))
x = bitrev(x)
m = 2
while m <= N:
for s in range(0,N,m):
for i in range (int(m/2)):
n = i * N / m
a, b = s + i, s + i + m/2
x[a], x[b] = x[(a)] + W[(n % N)] * x[(b)], x[(a)] - W
[(n % N)] * x[(b)]
m = m * 2
return x