FFT query

You can use the imaginary part to do another FFT at the same time or alternatively use a complex transform of half the length and a cunning twiddle factor to do a real to complex conjugate symmetric transform. There is a bit of pre/post processing to do to make this work.

See section 12.3 p617 in Numerical recipes.

If the Microship library FFT is any good it ought to have something to do this sort of transform already. Beware that some versions need a complex array that is one longer than the nominal 2^N.

Yes. You can compute the FFT of a real number in half the time. IIRC Numerical Recipes talks about how. (NR is a pretty good numerical methods book with some reasonably OK but not great code attached.)

Cheers

Phil Hobbs

Thanks! (And to Phil Hobbs) that's very useful.

Cheers

Bought the book, it arrived today. So much to learn, so little time!

Cheers

NR is mostly pretty good (a lot more reliable than DIY numerical algorithms) but they are slightly simplistic in places and were originally translated out of the FORTRAN so be a little careful.

C array bases index from 0 and FORTRAN from 1

This has the effect of disguising some things like BITREV indexing.

You might find that FFTW has something that will do what you want more or less off the peg and for any sane length of transform not just 2^N. The learning curve for it is a bit steep but there are examples and on the right compiler it is pretty much as fast as anything out there.

Another reasonable resource (though a bit dated now) is TI's:

Be sure to test the thing carefully after coding it.

Half the time because for real data streams the fft always has conjugate pairs for the imaginary side. So you only have to calculate half the bins and the other half are automatically the conjugate pairs