Re: [boost] FFT

From: nbecker_at_[hidden]
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/>

mQGiBDZa9ZcRBACYGMoAmHIBUR19lDLZNJhgxGtqVchV7OiwniGIE0UpwRj08fDX
/KO7/cXgXDZqFEgHF98e6Gbm4efyyC7seP4Ye8Av3n8h8PMv307lQieJd5qQVvwx
vwJWGHsX1EOsv/Suzb2ZcYllU4dgrdBIkRLQ5tsJPiWtxjsfBsONGqWmIwCghmQA
GayzNTFUUy0JkGP8SEJRycED/0GvchcxrSnN0FDe5HqM2YzNOnQYGEasAgRSNoG7
O87uudA3j+Hh4GQSD7VgleYArCXqfaNd8pj+EY0ykGjcTJk07aAl+Ib8UrQ8eNk/
RON0+/ZRN6QGqte1lokR969AgVFDQaHV0IctElZdpRg+JbKUiBn3iYaY7xfYYr1z
M6l/A/4v7HkRTfoMsEae+vhuatmekXpV7rrcmhAjLdaUWbamNrkp7N6fnDMQcRjJ
DA/9VBV8qjokGu2PEj+HQGZb52y1+/S+wmUbKlS/EkYMME9gEDuUBFhHlC6xbYg1
akcddicTFhNHtwNQ9GFliIaJzU1Mt7LumB03/Cy0A9PouNUhv7QhTmVhbCBELiBC
ZWNrZXIgPG5iZWNrZXJAZnJlZC5uZXQ+iFcEExECABcFAjZa9ZcDCwQDBRUDAgYB
AxYCAQIXgAAKCRCtdGDCLVoO090GAJsFFd/nUF315R0Snt97iV39JP/OTQCeNAaU
5MsmAJHGFcXXj9AkMRoguzu5AQ0ENlr1pRAEAKpFYKuYC++L4RuzreeuKObO15SS
LXgUo0A/q9Hm3VFQw/FaWShBilVKjw6C7lUFnajx0uzy3EhczjitdcHewXyOH/9T
1WyqtiJG9CJTRgQkA1vDSgLBqLQ8so4saOF0bT/66iaiBE9Rbl1yRvjJh5lIULJr
BG2WhHfh/xWl2KS/AAMFBACQ/DrlJe9ooOQAuuUFK8P1A1t4zN5u9gvVMLhpxnr+
KYFa4+GdP3939lRTb7smtVxh9gote66kTmH776sqx7Sn8/Vsx5DOEKpikTlQ9IPR
mXu8Oe9skh+rJcOrjSOH7fSsYqqH7O1GArw0l82bBwA6Xz86vWfyHj/Slo0YXxey
QohGBBgRAgAGBQI2WvWlAAoJEK10YMItWg7TDiEAn3kIiU3z9lbtF4UexjL8zWIv
QszbAJ4om+wo1penO8/y9uI0UOgJQZUtJg==
=Q5Ab
-----END PGP PUBLIC KEY BLOCK-----