Some Common FFT Misconceptions

Alan Peake wrote:

(snip)
> I wrote an FHT for the 80386 some years ago.
 > I used the 32 bit registers  and didn't
> do any scaling until the end. For a 8192 point
 > FHT (I think an FFT would be the same)
> this would have meant 13 right shifts with 16 bit 
 > registers so using 32 bit registers meant that at the end,
 > I shifted 3 to the left and just used the upper 16 bits of
 > the registers. Seemed to work OK although I didn't formally
 > calculate the round-off errors. I sort of felt that it
> would have been less than shifting at every stage.

Better than shifting at every stage, but is it still too much?

There can be a lot of cancellation in the additions such that
the final values are rarely 2**M times larger than the
inputs.  Maybe somewhat likely for the DC (f=0) term, but
much less likely for the others.  Some have suggested block
floating point, with one exponent for the whole block
(array).  If you do the whole transform in larger temporaries
and then find the largest magnitude at the end you can
shift appropriately.

-- glen