[Numpy-discussion] curious FFFT timing

[Eric Hagemann]

Scott,
    Right you are.  My brain fried -- I forgot about the other "small prime"
stuff

Inverse FFT (      4096) Number of seconds     5.508000 Time per FFT
0.005508
Forward FFT (      4096) Number of seconds     3.225000 Time per FFT
0.003225
Inverse FFT (      4097) Number of seconds    29.723000 Time per FFT
0.029723
Forward FFT (      4097) Number of seconds    26.788000 Time per FFT
0.026788

Cheers
Eric


----- Original Message -----
From: "Scott Ransom" <ransom at cfa.harvard.edu>
To: "Eric Hagemann" <ehagemann at home.com>
Cc: <Numpy-discussion at lists.sourceforge.net>
Sent: Tuesday, April 03, 2001 9:05 PM
Subject: Re: [Numpy-discussion] curious FFFT timing


> 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
>
> _______________________________________________
> Numpy-discussion mailing list
> Numpy-discussion at lists.sourceforge.net
> http://lists.sourceforge.net/lists/listinfo/numpy-discussion
>