Re: Fourier and FFT: Powers of 2 only?
- To: mathgroup at smc.vnet.net
- Subject: [mg16104] Re: Fourier and FFT: Powers of 2 only?
- From: Robert Knapp <rknapp>
- Date: Thu, 25 Feb 1999 08:25:00 -0500
- Organization: Wolfram Research, Inc.
- References: <7a29pk$1pm@smc.vnet.net> <7ag1cm$aef@smc.vnet.net> <7ao3lc$ruk@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
For Mathematica version 3, John Doty is correct...
John Doty wrote:
>
> 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}
>
In the version under development a number of improvements have been made
which will make Fourier generally faster, and changes the situation in a
number of ways.
For the general case, it will still use a mixed radix algorithm
For lengths which are products of small primes (also 4,8,16 and 9) it
uses a self-sorting prime factor algorithm, (after Temperton), which in
many cases is faster that even the radix 2 with bit reversal.
For large prime factors it uses an algorithm which is about three times
slower than for a nearby factorable number, but much faster than the
usual O(n^2) algorithm for prime factors.
Rob Knapp
Wolfram Research