From: Eric H. <eha...@ho...> - 2001-04-04 01:11:02
|
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" <ra...@cf...> To: "Eric Hagemann" <eha...@ho...> Cc: <Num...@li...> 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: ra...@cf... Cambridge, MA 02138 > GPG Fingerprint: 06A9 9553 78BE 16DB 407B FFCA 9BFA B6FF FFD3 2989 > > _______________________________________________ > Numpy-discussion mailing list > Num...@li... > http://lists.sourceforge.net/lists/listinfo/numpy-discussion > |