Boost logo

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

(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

Boost list run by bdawes at, gregod at, cpdaniel at, john at