help-octave
[Top][All Lists]

## Re: FFT inaccuracy

 From: Jonathan M Hill Subject: Re: FFT inaccuracy Date: Thu, 30 Apr 1998 14:37:53 -0400 (EDT)

```Hello;

Just a follow up question from a newbie...I guess this question
is directed at the fft() function.  I don't want to make noise, but
I'm just a bit curious...

How can you possibly produce a ``Fast-Fourier Transform'' from
five points?  A radix-2 FFT requires a number of points equal to a
power of two.  A radix-4 FFT requires...(so on, so forth)  Since five
is prime, even a mixed radix FFT won't do.

How does the fft() function handle a situation when the number of
points is not a power of the radix?  Does it matter?  Does the function
resort to the definition of the discrete Fourier Tranform?  If thats the
case, this may explain the lack of accuracy.

Jonathan Hill

On Thu, 30 Apr 1998, Dirk Laurie wrote:

> >> ifft(fft([1 1 0 0 1]))
> ans =
>     1.0000e+00    1.0000e+00   -1.4682e-08   -1.4682e-08    1.0000e+00
>
> This seems to indicate a lack of accuracy.  And indeed, comparison with
> the exact value shows
>
> >> fft([1 1 0 0 1])-[3, sin(3*(1:4)*pi/5)./sin((1:4)*pi/5)]
> ans =
>     0.0000e+00    1.6415e-08   -1.6415e-08   -1.6415e-08    1.6415e-08
>
> This suggests some single-precision constant in the radix-5 special case.
> The error does not occur with n=7:
>
> >> ifft(fft([1 1 0 0 0 0 1]))
> ans =
>  Columns 1 through 5:
>     1.0000e-00    1.0000e+00   -7.8064e-16    1.2067e-16    1.2067e-16
>  Columns 6 and 7:
>    -7.8064e-16    1.0000e+00
>
> Dirk Laurie
>
>

```