Re: [boost] FFT

From: John Suters (johnds_at_[hidden])
Date: 2001-10-31 16:46:26

> 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.

It's in Knuth, volume 2 as well.

> 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.

Yes, it's a very good point, and one which I didn't mention in my original
email. My whole reason for constructing this function was as an auxiliary
for a fixed precision integer class multiplication routine. Consequently,
all I've ever done with it is do 2 transforms, pointwise multiply and then
take the inverse. I always chuck away any index greater than the precision
of my integer( note - fixed precision, not arbitary), so I've never really
cared about the length of the output. Anything greater than my precision I
consider to be overflow.
It's also the reason for the algorithm's inclusion in the reference, as well
as it's inclusion in Knuth, volume 2.

Perhaps my proposal would be better phrased as an FFT implementation for use
in large bit-magnitude multiplication routines.