       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:=
> Timing[Fourier[Take[dat,65536]];]
>
> Out=
> {2.08333 Second,Null}
>
> The worst is when the length is prime:
>
> In:=
> Timing[Fourier[Take[dat,65537]];]
>
> Out=
> {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:=
> Timing[Fourier[Take[dat,64000]];]
>
> Out=
> {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

```

• Prev by Date: Stop palette opening
• Next by Date: Using "Fit"
• Previous by thread: Re: Fourier and FFT: Powers of 2 only?
• Next by thread: Re: Bug?