Re: Fourier and FFT: Powers of 2 only?
- To: mathgroup at smc.vnet.net
- Subject: [mg16037] Re: Fourier and FFT: Powers of 2 only?
- From: John Doty <jpd at w-d.org>
- Date: Sun, 21 Feb 1999 00:15:15 -0500
- Organization: The Internet Access Company, Inc.
- References: <7a29pk$1pm@smc.vnet.net> <7ag1cm$aef@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Fourier[] uses a "mixed radix" FFT algorithm, in which the transform is
decomposed into subtransforms whose lengths are the prime factors of the
length of the data set. The efficiency of this procedure depends on
small the factors are. The best is when the length is a power of 2:
In[8]:=
Timing[Fourier[Take[dat,65536]];]
Out[8]=
{2.08333 Second,Null}
The worst is when the length is prime:
In[9]:=
Timing[Fourier[Take[dat,65537]];]
Out[9]=
{5673.85 Second,Null}
It's still pretty good if all the factors are small, even if you can't
get all the way down to 2:
In[10]:=
Timing[Fourier[Take[dat,64000]];]
Out[10]=
{3.8 Second,Null}
Jim Jennings wrote:
>
> In article <7a29pk$1pm at smc.vnet.net>, "Peltio" <pelt.ioNOS at PAMiol.it> wrote:
>
> >Since FFT procs work best with sets of points whose number is a power of
> >2, what does Fourier[] do when it's fed a set of, say, 200 points? Will
> >it extend to 256 by adding zeros, or split it in subsets that are power
> >of 2, or whatever?
>
> Fourier[] definately works on any number of points without zero padding.
> I'm not sure how it works, but I suspect it has some kind of adaptive
> algorithm that breaks up the list into the smallest number of power 2
> lists as possible. I also suspect that the speed of Fourier[] depends on
> how "close" your list is to a simple integer power of 2, but I have not
> tested it. In my applicaions it has always been fast enough that I
> haven't bothered to think about it.
>
> --
> Jim Jennings
> Research Associate jenningsj at mail.utexas.edu
> Bureau of Economic Geology (512) 471-4364 (voice)
> University of Texas at Austin (512) 471-0140 (fax)
--
John Doty "You can't confuse me, that's my job."
Home: jpd at w-d.org
Work: jpd at space.mit.edu