Prev: C API: module cleanup function
Next: pyjon: pythonic javascript interpreter
From: uche on 30 Jan 2010 13:33
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
From: Stefan Behnel on 30 Jan 2010 13:52
uche, 30.01.2010 19:33:
> I have the following FFT python code

You didn't seriously implement an FFT in plain Python code, did you? FFTs
are amongst the first thing that come to my mind when I try to imagine what
I'd use NumPy for. (and I *never* used it!)

Stefan
From: MRAB on 30 Jan 2010 14:08
uche wrote:
> 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.
>
Which version of Python are you using? In Python 3 the division operator
'/' returns a float, whereas in Python 2 it returns an int if both
operands are int. In Python 3 the int division operator is '//', which
is also accepted in recent versions of Python 2.

[snip]
>
> os.path.exists("input.csv")
>
> fin=open('input.csv', 'r')
>
> for line in fin: #read the line from the file
>
> array=line.split(',')
>
These lines should be indented more:

> for a in range(len(array)): #convert into integers
>
> array2.append((array[a]))
>
array2.append(int(array[a]))

[snip]

From: uche on 30 Jan 2010 14:18
On Jan 30, 2:08 pm, MRAB <pyt...(a)mrabarnett.plus.com> wrote:
> uche wrote:
> > 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.
>
> Which version of Python are you using? In Python 3 the division operator
> '/' returns a float, whereas in Python 2 it returns an int if both
> operands are int. In Python 3 the int division operator is '//', which
> is also accepted in recent versions of Python 2.
>
> [snip]
>
> >     os.path.exists("input.csv")
>
> >     fin=open('input.csv', 'r')
>
> >     for line in fin:    #read the line from the file
>
> >         array=line.split(',')
>
> These lines should be indented more:
>
> >     for a in range(len(array)): #convert into integers
>
> >         array2.append((array[a]))
>
>           array2.append(int(array[a]))
>
> [snip]

Thanks, I just got this code from a site and trying to compile it.
it's just a nightmare!
I got another problem after changing / to // . Yes, I am using 3.1.

W.append(exp(sign * 2j * pi * i // N))
TypeError: can't take floor of complex number.

From: Stefan Behnel on 30 Jan 2010 14:21
Stefan Behnel, 30.01.2010 19:52:
> uche, 30.01.2010 19:33:
>> I have the following FFT python code
>
> You didn't seriously implement an FFT in plain Python code, did you?

Sorry, no, you didn't. Should have read your post a little closer.


> FFTs
> are amongst the first thing that come to my mind when I try to imagine what
> I'd use NumPy for. (and I *never* used it!)

On second thought, I'd probably use FFTW for that, and there seem to be
Python bindings for it:

http://developer.berlios.de/projects/pyfftw/

Stefan
 |  Next  |  Last
Pages: 1 2 3
Prev: C API: module cleanup function
Next: pyjon: pythonic javascript interpreter