Boost logo

Boost :

From: George A. Heintzelman (georgeh_at_[hidden])
Date: 2001-10-31 14:44:37


> Would there be any interest in a fast fourier transformation class?

I'm sure there would be. In my past life, I would have been. ;)

> I've written one that has the following signature:
>
> template<class DOUBLE,
> class COMPLEX = std::complex<DOUBLE>,
> class VECTOR = std::vector<COMPLEX> >
> class fft
> {
> static inline void transform(VECTOR&, bool);
> };

I don't think that this is the right signature. It's not in keeping
with the STL. First of all, I think that the transform should be an
algorithm, not a class. Second, it should take iterators, not
containers. Thus, in keeping with the STL, it should probably be:

template<class ForwardIterator, class OutputIterator>
void fast_fourier_transform(ForwardIterator start, InputIterator end,
                            OutputIterator out)

This avoids the whole need for default template arguments, and allows
one to non-destructively transform if desired, or convert only a
portion of a sequence. And I doubt it would be hard to convert your
existing implementation to this signature...

One caveat: be sure that your implementation internally is going to
work for generalized numeric classes. You may well need a way to say
math_constants::pi<type> (where type might be std::complex<boost::ration
al<int> > for example) or the equivalent -- I think this is a great
example in practice that could help clarify all the recent discussion
of how to specify the interface to constants...

> The bool parameter on the transform specifies whether we're taking
> the inverse or not, and defaults to false.

I'm not sure that this is the best from a user's POV. I think I'd be
continually looking up which value is the one I want. I'd prefer to see
two functions (fft, inverse_fft) which are implemented in terms of the
same function with a +- toggle. As an alternative (or as an additional
user-visible interface for use when you really want to toggle at
runtime) you could provide a named enum instead of a bool.

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.

George Heintzelman
georgeh_at_[hidden]


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk