FFT coding help

Hi, I've just coded an easy fft program. You can find it here:
http://rapidshare.com/files/147982232/fft.tar.gz.html

Compile it with gcc -lm -I. fft.c ep.c
and then run a.out.

As you'll see, it takes about 0.5 seconds to do a length-8192 FFT. I think
that's a very bad time. Compared to other fft this is a factor of ~1000.
What has to be improved?

Thanks,
Hugo 

On Sep 24, 9:09&#4294967295;am, "relative" <hugoplat...@aon.at> wrote:
> Hi, I've just coded an easy fft program. [...]
> As you'll see, it takes about 0.5 seconds to do a length-8192 FFT. I think
> that's a very bad time. Compared to other fft this is a factor of ~1000.
> What has to be improved?

Actually, it's more like a factor of 5000 (e.g. FFTW, www.fftw.org,
does a length-8192 double-precision FFT of complex data in under 100
microseconds on a 2.66GHz Intel Core 2).

When your code is that far off in performance, there's no point in
trying to improve it incrementally.  Its structure is fundamentally
wrong, and you should throw it out and start over.  Look at how other
FFT programs do it.  For example, I would recommend looking at the FFT
code by Ooura (http://www.kurims.kyoto-u.ac.jp/~ooura/index.html),
which is fairly easy to understand and is still quite fast.  (The
fastest programs are significantly faster, but a lot more
complicated.)

I'm assuming you want to do this as a learning exercise; as a
practical matter, you should just download one of the many free FFT
implementations out there rather than writing yet another one.

Regards,
Steven G. Johnson