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@cfa.harvard.edu Cambridge, MA 02138 GPG Fingerprint: 06A9 9553 78BE 16DB 407B FFCA 9BFA B6FF FFD3 2989