Re: Fourier transform
- To: mathgroup at smc.vnet.net
- Subject: [mg14104] Re: Fourier transform
- From: Robert Knapp <rknapp>
- Date: Fri, 25 Sep 1998 03:15:28 -0400
- Organization: Wolfram Research, Inc.
- References: <6tp01u$2gh@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Jens-Peer Kuska wrote:
>
> Hi David,
>
> I don't know the code but the restriction of the usual fast Fourier
> transfrom to
> data sets of length 2^n comes from the radix 2 based integer
> representation in the most computers.
This has nothing to do with it whatsoever.
The usual FFT depends on factoring the length of the input into smallish
integers. Basically, DFT's of the size of the small integer factors
are combined to produce the FFT of the entire input.
Powers of two are relatively simple because the combination (and the
DFT's of size 2) are quite simple. Hence, they are usually fast.
However, with small factors, the complexity is still reasonable if the
lenght is not a power of 2. When you get into problems is if the
length is a large prime, or has a large prime factor.
> I think Mathematica is so clever
> that it will use the fast version of the fft when ever possible.
In version 3, this is not quite true. It doesn't use a fast algorithm
for prime lengths or lengths with large prime factors.
In the development verion, by using convolution, these are done in O(N
log(N)) complexity (albeit with a constant about 3 times higher than
for factorable length).
>
> You can try it out that
> In[1]:=
> data=Table[Random[],{i,8,1024},{n,1,i}]; In[3]:=
> tm= First /@ (Timing[Fourier[#]] & /@ data); In[5]:=
> ListPlot[tm /. Second->1]
>
> gives not propto N^2 plot with some drastic smaller timing results at
> Length[data[k]]==2 ^M_Integer.
>
> Regards
> Jens
>
> -----Original Message-----
> From: David Annetts <dannetts at laurel.ocs.mq.edu.au> To:
To: mathgroup at smc.vnet.net
> mathgroup at smc.vnet.net
> Subject: [mg14104] [mg13954] Re: Fourier transform
>
> >Hi Jens-Peer
> >
> >> Fourier[] implements a numerical fast fourier transform. That means that
> >> the data passed to Fourier[] are the function values f(t) on the
> >> interval t in [0,2Pi) with constant increment. The data are assumed to
> >> be periodic in t with period 2Pi.
> >
> > My understanding was that Fourier implemented a Discrete Fourier
> >Transform as a general case, and a Fast Fourier Transform if your data
> >length an integer power of 2.
> >
> >--
> > ==================================================================
> > David Annetts _____________
> > http://www.ocs.mq.edu.au/~dannetts/ |C R C A M E T|
> > |-------------|
> > |_____ |
> > CRC for Australian Mineral |````` \ |
> > Exploration Technologies |`````/$\ |
> > Earth Sciences |````/$$$\____|
> > Macquarie University, NSW 2109 |```/$$$/.....|
> > AUSTRALIA |``/$$$/......|
> > phone: +(1-61-2) 9850 9280, fax (1-61-2) 9850 8366 -------------
> > ==================================================================
> >
> >
> >