Re: [Numpy-discussion] curious FFFT timing

[Scott R. <ra...@cf...>]

Hi Eric,

> Any one want to speculate on the timing difference for the 4095 vice
> 4096 long transforms ?
> Since 4095 is not a power of two I would have expected a greater time
> difference (DFT vice FFT)

You are correct in that 4095 is not a power of two, but is is the
product of only small prime factors:
3 * 3 * 5 * 7 * 13 = 4095

Since the FFT code implements a N*log_2(N) algorithm for numbers that
contain only small prime factors, the difference in times is rather
small.  FFTs that have lengths that are powers-of-two tend to be more
efficient in general (since the decimation routines are cleaner for this
case).

If you test with 4097 (17 * 241) it will be quite a bit slower I'd
guess...

Scott


-- 
Scott M. Ransom                   Address:  Harvard-Smithsonian CfA
Phone:  (617) 495-4142                      60 Garden St.  MS 10 
email:  ra...@cf...              Cambridge, MA  02138
GPG Fingerprint: 06A9 9553 78BE 16DB 407B  FFCA 9BFA B6FF FFD3 2989