[Numpy-discussion] curious FFFT timing

[Eric H. <eha...@ho...>]

I have an application that needs to perform close 1/2 million FFT's =
(actually inverse FFTs)  I was stymied by the time it was taking so I =
created a simple benchmark program to measure raw fft speed - hoping to =
extrapolate and see if the FFT algorithm was the time consuming portion =
of the algorithm.

The result I obtained surprised me

Inverse FFT (      4096) Number of seconds     5.608000 Time per FFT     =
0.005608
Forward FFT (      4096) Number of seconds     3.164000 Time per FFT     =
0.003164
Inverse FFT (      4095) Number of seconds     8.222000 Time per FFT     =
0.008222
Forward FFT (      4095) Number of seconds     5.468000 Time per FFT     =
0.005468
Inverse FFT (      8192) Number of seconds    12.578000 Time per FFT     =
0.012578
Forward FFT (      8192) Number of seconds     7.551000 Time per FFT     =
0.007551

Inverse FFTs were taking almost twice as long as forward FFTs !

Bottom line I found that in the inverse code the multiplication of 1/N =
at the end was the culprit.

When I removed the /n from the line=20

return _raw_fft(a, n, axis, fftpack.cffti, fftpack.cfftb, _fft_cache)/n  =


the code timing was more along the line of what was expected.

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)

N*N / N*log2(N) =3D N/log2(N) =3D 4096/12 =3D 341.33 which is >> than =
the 1.72 seen above

Cheers
Eric

------------------------------------ Code Snippet =
---------------------------------------------

import time
from Numeric import *
from FFT import *


def f_fft(number,length):

    a =3D arange(float(length))
    start_time =3D time.time()
   =20
    for i in xrange(number):
        b =3D fft(a)

    durat =3D time.time() - start_time
    durat_per =3D durat / number
    print "Forward FFT (%10d) Number of seconds %12.6f Time per FFT =
%12.6f" % (length,durat,durat_per)
   =20
def i_fft(number,length):

    a =3D arange(float(length))
    start_time =3D time.time()
   =20
    for i in xrange(number):
        b =3D inverse_fft(a)

    durat =3D time.time() - start_time
    durat_per =3D durat / number
    print "Inverse FFT (%10d) Number of seconds %12.6f Time per FFT =
%12.6f" % (length,durat,durat_per)



i_fft(1000,4096)
f_fft(1000,4096)
i_fft(1000,4095)
f_fft(1000,4095)
i_fft(1000,8192)
f_fft(1000,8192)