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