Re: [boost] FFT

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]