Date: 2001-10-31 16:10:32
>>>>> "John" == John Suters <johnds_at_[hidden]> writes:
>> FFT isn't restricted to powers of 2.
John> Then that's a limitation of my implementation and understanding of the
John> problem then. My understanding was that if you allowed for the input being a
John> power of two, padding if required with complex(0,0), then the FFT (or at
John> least the recursive implementation) would work as desired. That's my reading
John> of "Introduction to Algorithms", Cormen, Leiserson and Rivest.
I'm not familiar with this reference. I'm also not very familiar with
recursive implementation, but my guess is that recursion would not
limit you to powers of 2.
John> Is this incorrect? If not, would I be better off completely hiding this from
John> the user and simply copying back into the input range whatever values we get
John> that fit?
When you say, "would work as desired", I guess the question is, what
do you desire? I would say, that if you want to provide a truly
general fft, then it should be as free from arbitrary limitations as
practical. I would say that limiting to only powers of two is not
very general. You can pad up to a power of two and compute the fft
coefficients of the result, BUT there is no simple relation between
the desired result, which is an M pt fft, and the coefficients you
computed by padding.
-----BEGIN PGP PUBLIC KEY BLOCK-----
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: Processed by Mailcrypt 3.5.6 and Gnu Privacy Guard <http://www.gnupg.org/>
-----END PGP PUBLIC KEY BLOCK-----
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk