Re: Newbie questions inspired by Re: Complexity of not 2^n FFT

>>2. Can someone point me to description of how one would combine "small
>>FFT's" to make a "large FFT"? Here i also suspect the explanation
>>would be illuminating of how/why FFT/FT works.
>
>Ya know, I'm startin' to think that there
>may well be a way to do this
>(if there's no time gap between the time-domain
>samples used to compute the "small size" FFTs).

Combining small FFTs to make large FFTs is, in fact, the whole point of 
how the most common FFT algorithm (Cooley-Tukey) works (as well as some 
other FFT algorithms such as the Prime-Factor Algorithm).  See also:

	http://en.wikipedia.org/wiki/Cooley-Tukey_FFT_algorithm

Cooley-Tukey works by taking an DFT of a composite size n = n1*n2 and 
expressing it as smaller DFTs of size n1 and n2, recursively, along with 
multiplication by phase factors called "twiddle factors".  You can 
derive the basic recursive step, for any n1 and n2, in two lines of 
algebra (see the equation at the end of the "general factorizations" 
section of the above page).

The only trick is that the smaller transforms are not of *consecutive* 
data, as you imply above, but are rather of *interleaved* data.

For example, you could express a transform of size 64 as:

	1) four transforms of size 16, operating on: the multiples of 4, 
the multiples of 4 plus 1, the multiples of 4 plus 2, and the multiples 
of 4 plus 3

	2) multiplication by twiddle factors

	3) 16 transforms of size 4

Given fast FFTs of size 16 and 4, you are done.  You might ask whether
the transforms of size 4 are on consecutive or interleaved data.  The
answer is that if the transform is done in-place, they are consecutive,
but then the output is in scrambled order.  Alternatively you do step
(1) with interleaved inputs but consecutive *outputs* (i.e. 
transposing), and then do the transforms of size 4 on interleaved data
(multiples of 16, multiples of 16 plus 1, etcetera), resulting in
in-order output.

Now, if you could instead do the first step on consecutive data, as you 
suggest, that would be very useful for the case where, say, only the 
first 1/4 of the data is non-zero: you would asymptotically save a 
factor of ~4 in time.  However, as far as I know, this is not possible.  
(The savings that one can achieve from such a "pruned FFT", as it is 
called in the literature, generally occur only in the log of N log N.)

Cordially,
Steven G. Johnson