Re: Some Common FFT Misconceptions

On Sat, 29 Mar 2008 13:40:28 -0700 (PDT), "Steven G. Johnson"
<stevenj@xxxxxxxxxxxx> wrote:

(Snipped by Lyons)

By the way, in answer to Andrew's question about whether this depends
on the implementation style: yes and no.

For example, suppose you perform your FFT in single precision, whereas
you do all of your naive DFT summations/multiplications in double or
extended precision (either explicitly or because your CPU is set in
extended-precision mode and the operations stay in registers) and you
only round to single precision at the end. The FFT errors will still
grow as O(sqrt(log N)) on average, while the naive DFT errors will
still grow as O(sqrt N) on average. However, the constant factor in
the latter will be much smaller thanks to the higher intermediate
precision, so the naive DFT in that case may in fact be more accurate
until N grows very large.

Also, of course, there are a few ways to screw up your FFT accuracy---
most commonly, if you compute your trigonometric constants using an
inaccurate recurrence formula.

See also fftw.org/accuracy for accuracy benchmarks of various FFT
implementations---they are all basically the same, except for a
handful that use unstable trig. recurrences, and illustrate how
remarkably slow the roundoff error growth can be.

Steven

Hello Steven,
Thanks for takin' the time to post such
useful, practical, information.

By the way, congratulations on having your (and
M. Frigo's) efforts, regarding your FFTW work,
described in such glowing terms in the
"From the Editor" message of the March Issue
of the IEEE Signal Processing magazine.
That message is on page 2 of the magazine and
is terrifically complimentary. Neat!

[-Rick-]
.

Relevant Pages

  • Re: Some Common FFT Misconceptions
    ... more accurate than evaluating the naive DFT formula directly by two ... The mean relative errors of the C-T FFT grow as ... whereas for the naive DFT it is O; ... For example, suppose you perform your FFT in single precision, whereas ...
    (comp.dsp)
  • Re: Bitwidth required for an 8K point FFT
    ... By extrapolating the graph in Fig. 12-9, an 8k point FFT, ... round-off noise, using single precision floating point. ...
    (comp.dsp)
  • Re: single precision
    ... Are all intermediate calculations within fft in single ... that's the implication of the above article. ...
    (comp.soft-sys.matlab)
  • Re: single precision
    ... single precision variables, of course, but I wouldn't ... necessarily expect that all of the functions that support ... FFT, it's possible for local variables to be in double precision (or ...
    (comp.soft-sys.matlab)