Boost :

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.

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]