[Numpy-discussion] performance of real_fft with fftpacklite.c

[Scott Ransom]

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