Re: FFT inaccuracy

[Jonathan M Hill]

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
                                                   address@hidden

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
> 
>