[Numpy-discussion] curious FFFT timing
Scott Ransom
ransom at cfa.harvard.edu
Tue Apr 3 20:05:13 CDT 2001
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: 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