[Numpy-discussion] performance of real_fft with fftpacklite.c
Scott Ransom
ransom at cfa.harvard.edu
Fri Nov 3 10:43:36 EST 2000
Bernd Rinn wrote:
>
> Hello,
>
> does anyone know why the performance of FFT.real with fftpacklite.c is
> so unballanced for n=2**i and different values of i? My example is:
Hi,
The problem is that your routine gives arrays of length 2**n-1 not
2**n! So for the arrays where the CPU time is huge, you are FFTing a
length that is a prime number (or at least not easily factorable).
FFTPACK has to do a brute force DFT instead of a FFT! (Ah, the beauty
of n*log(n)...)
You can see that this is the case by printing the lengths of the arrays:
-------------------------------
from Numeric import array,Float
from FFT import real_fft
from time import time
i=1
while i<20:
n = 2**long(i)
a=array(range(long(1),n),Float)
print len(a)
i=i+1
-------------------------------
What you should try instead is the following:
-------------------------------
from Numeric import arange,Float
from FFT import real_fft
from time import time
i=1
while i<20:
n = 2**i
a=arange(n, typecode=Float)
anfang = time()
b = real_fft(a)
ende=time()
print "i=", i, " time: ", ende-anfang
i=i+1
-------------------------------
Which gives the following run-times on my Pentium 450 under Linux:
i= 1 time: 0.000313997268677
i= 2 time: 0.000239014625549
i= 3 time: 0.000229954719543
i= 4 time: 0.000240087509155
i= 5 time: 0.000240087509155
i= 6 time: 0.000257968902588
i= 7 time: 0.000322103500366
i= 8 time: 0.000348091125488
i= 9 time: 0.000599980354309
i= 10 time: 0.000900983810425
i= 11 time: 0.0018150806427
i= 12 time: 0.00341892242432
i= 13 time: 0.00806891918182
i= 14 time: 0.0169370174408
i= 15 time: 0.038006067276
i= 16 time: 0.0883399248123
i= 17 time: 0.199723005295
i= 18 time: 0.661148071289
i= 19 time: 0.976199030876
Hope this helps,
Scott
--
Scott M. Ransom Address: Harvard-Smithsonian CfA
Phone: (617) 495-4142 60 Garden St. MS 10
email: ransom at cfa.harvard.edu Cambridge, MA 02138
GPG Fingerprint: 06A9 9553 78BE 16DB 407B FFCA 9BFA B6FF FFD3 2989
More information about the NumPy-Discussion
mailing list