Re: [boost] FFT

From: George A. Heintzelman (georgeh_at_[hidden])
Date: 2001-10-31 16:16:02

> > template<class ForwardIterator, class OutputIterator>
> > void fast_fourier_transform(ForwardIterator start, InputIterator end,
> >                             OutputIterator out)
> 
> I agree in principle. The reason I thought of it this way is so that I could
> use std::complex to make it clear that I wasn't going to start mucking
> around converting doubles into complex, or ints into complex and so on. I
> guess if the iterator doesn't point to a complex then it won't compile...

Or more precisely, if the iterator doesn't point to a type for which 
the algorithm's operations are meaningful, it won't compile. That's the 
behavior that you want. I suspect (though I don't know) that fourier 
transform algorithms might be useful when working with quaternions, for 
example.

(NB: I think you do need to worry about the common case where the input 
sequence are real. In that case)

> I'm not sure what you mean by non-destructively transform.

If I understand what you meant in your proposal, you would start with a 
vector V containing n elements (lets say for simplicity its a power of 
two right now); and at the end, V would contain n different elements. 
You've lost the original vector. So if you wanted to (or had to because 
of a function signature) keep the original values, you would have to 
make a copy. This should be avoided.

Instead, the input and output should be considered wholly separate, and 
the production of the output should not modify in any way the input.

If I misunderstood your proposal, I apologize.

> > You should consider also whether you want to make allowances for the
> > more general fourier transform case when the size of the output range
> > of interest does not equal the size of the input range.
> 
> Hmmm. Perhaps I'm out of my depth here. My function always extends the
> vector to the minimum power of two to contain the input. Is this what you
> mean by this?

In mathematics, the fourier transform is a mapping from one continuous 
function of n variables to another continuous function of n conjugate 
variables. In computing, we discretize these functions, and the FFT 
algorithms provide some fast ways of doing this when we have 
discretized the function in 2^m steps. But there is no a priori reason 
that a user of a fourier transform will have at his disposal an easily 
accessible power of two; or they may know something about the function 
they are inputting, and thus know that only a specific range of the 
conjugate variables will be of interest.

I am not suggesting that you write the algorithms to deal with these 
things; that would be hard. All I am suggesting is that we consider the 
interface such that it might be generalized in these directions, for 
differently inclined users.

George Heintzelman
georgeh_at_[hidden]