<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META http-equiv=Content-Type content="text/html; charset=iso-8859-1">
<META content="MSHTML 5.50.4611.1300" name=GENERATOR>
<STYLE></STYLE>
</HEAD>
<BODY bgColor=#ffffff>
<DIV><FONT face=Arial size=2>I have an application that needs to perform close
1/2 million FFT's (actually inverse FFTs) I was stymied by the time it was
taking so I created a simple benchmark program to measure raw fft speed - hoping
to extrapolate and see if the FFT algorithm was the time consuming portion of
the algorithm.</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>The result I obtained surprised
me</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>Inverse FFT ( 4096)
Number of seconds 5.608000 Time per
FFT 0.005608<BR>Forward FFT
( 4096) Number of seconds
3.164000 Time per FFT 0.003164<BR>Inverse FFT
( 4095) Number of seconds
8.222000 Time per FFT 0.008222<BR>Forward FFT
( 4095) Number of seconds
5.468000 Time per FFT 0.005468<BR>Inverse FFT
( 8192) Number of seconds
12.578000 Time per FFT 0.012578<BR>Forward FFT
( 8192) Number of seconds
7.551000 Time per FFT 0.007551</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>Inverse FFTs were taking almost twice as long as
forward FFTs !</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>Bottom line I found that in the inverse code the
multiplication of 1/N at the end was the culprit.</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>When I removed the /n from the line </FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>return _raw_fft(a, n, axis, fftpack.cffti,
fftpack.cfftb, _fft_cache)/n </FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>the code timing was more along the line of what was
expected.</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>Any one want to speculate on the timing difference
for the 4095 vice 4096 long transforms ?</FONT></DIV>
<DIV><FONT face=Arial size=2>Since 4095 is not a power of two I would have
expected a greater time difference (DFT vice FFT)</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>N*N / N*log2(N) = N/log2(N) = 4096/12 = 341.33
which is >> than the 1.72 seen above</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>Cheers</FONT></DIV>
<DIV><FONT face=Arial size=2>Eric</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>------------------------------------ Code Snippet
---------------------------------------------</DIV>
<DIV><BR>import time<BR>from Numeric import *<BR>from FFT import *</DIV>
<DIV> </DIV>
<DIV><BR>def f_fft(number,length):</DIV>
<DIV> </DIV>
<DIV> a = arange(float(length))<BR>
start_time = time.time()<BR> <BR> for i in
xrange(number):<BR> b = fft(a)</DIV>
<DIV> </DIV>
<DIV> durat = time.time() - start_time<BR>
durat_per = durat / number<BR> print "Forward FFT (%10d)
Number of seconds %12.6f Time per FFT %12.6f" %
(length,durat,durat_per)<BR> <BR>def
i_fft(number,length):</DIV>
<DIV> </DIV>
<DIV> a = arange(float(length))<BR>
start_time = time.time()<BR> <BR> for i in
xrange(number):<BR> b =
inverse_fft(a)</DIV>
<DIV> </DIV>
<DIV> durat = time.time() - start_time<BR>
durat_per = durat / number<BR> print "Inverse FFT (%10d)
Number of seconds %12.6f Time per FFT %12.6f" % (length,durat,durat_per)</DIV>
<DIV> </DIV>
<DIV> </DIV>
<DIV> </DIV>
<DIV>i_fft(1000,4096)<BR>f_fft(1000,4096)<BR>i_fft(1000,4095)<BR>f_fft(1000,4095)<BR>i_fft(1000,8192)<BR>f_fft(1000,8192)</DIV>
<DIV> </DIV>
<DIV> </DIV></FONT></BODY></HTML>