unencountered error in FFT python

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

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
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.

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


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

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


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


    print (fft(array2))
    print (("It took"),Tf-Ti,("seconds to calculate an FFT of
    #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

More information about the Python-list mailing list