**Subject:** Re: SETI@home clients being built

**To:** Aaron J. Grier *<agrier@poofy.goof.com>*

**From:** Bill Studenmund *<wrstuden@nas.nasa.gov>*

**List:** current-users

**Date:** 06/21/1999 10:57:29
On Sat, 19 Jun 1999, Aaron J. Grier wrote:
> On Sun, Jun 20, 1999 at 07:03:18AM +0900, Izumi Tsutsui wrote:
>
> > Yes, it seems doing many FFTs.
>
> Hmm... I was always under the assumption that the FFT was by definition
> an optimized discrete Fourier transform, and thus no floating point was
> used.
FFT is an algorythm for doing an FT (a Fourier Transform) more
efficiently. If I remember my algorythms right, FT's are O(N^2) while FFT
is O(N log(N)). O() describes how the maximum bound grows as you increase
the number of elements in your sample (i.e. the number of samples you're
transforming). The main thing is that FFT grows more slowly than FT, so
for big vectors, it makes a big difference.
The format of your data stream (the signal you're (F)FT'ing) dictates the
choice between integer and FP math - it's orthogonal to the algorythm
choice. :-)
Take care,
Bill