Re: [boost] ffts

From: Gabriel Dos Reis (gdr_at_[hidden])
Date: 2002-09-22 03:02:42

Jason D Schmidt <jd.schmidt_at_[hidden]> writes:

| On this list, I have discussed submitting my fft code to Boost.  Some of
| the feedback I have received was:
| 
| The interface should be generic:
|     should be able to do arrays whose size is a power of 2 & not a power
| of 2
|     should be able to transform any container generically
|     should be able to do real or complex data
|     if feasible, it might be useful to handle integer & floating point
| data
| 
| Here is the current state of my fft code with respect to the above
| points:
| 
| The prototype is:
| template <const size_t cPoints, class value_type>
| std::valarray<std::complex<value_type> > fft(const
| std::valarray<std::complex<value_type> >& data).

This prototype suggests that you're not computing "in-place".  That is
regrettable because that is commonly used.
However, it would worth investigating how much of the abstraction penalty
the Named Return Value Optimization removes.

| When one performs an n-point fft, the first thing that has to be done is
| to calculate the bit-reversal of the indices (it's the critical part of
| the algorithm).  The bit-reversed indices are different for each
| different fft size.  With my code, a 128-point fft is a different
| function from a 256-point function (because the size is a template
| parameter).

If you're only offering a compile-time size, then it may worth
calculating also the bit-reverse array at compile-time without using a
valarray object.  However, I don't know how that complicates your design.

[...]

| The drawback to this design is that the size of the fft has to be known
| at compile time (because it's a template parameter), and it makes other
| computations (psd, correlation, convolution, etc.) that depend on the fft
| very cumbersome.

Indeed, it reduces the library scope.  

Did you consider http://www.fftw.org/ to see how you may use
pre-computed code paths with the algorithm that accepts dynamically
sized input arrays? 

| Plus, the fft size has to be a power of 2.  However, I
| could pad the input data with zeros so that it has a size which is a
| power of 2.
| 
| Also, the above prototype shows that my fft function can't handle any
| container generically.  I implemented it for only the std::valarray
| because valarray has functionality that makes it much faster than any
| other standard container.  For example, inside the fft function if I want
| to write code like
| 
| static const std::valarray<size_t> bit_reversed
| indices(do_bit_reversal<cPoints>());
| const std::valarray<value_type> bit_reversed_data[bit_reversed_indices] =
| data;
| 
| there's no container-generic way to do it.  I can't assume that every
| container will have an operator[] that takes a generic container of
| size_t variables.  In fact, valarray is the only standard container with
| that capability (along with std::slice & std::gslice capabilities).

Indeed.  One of the original intent of valarray is to treat
"array-expressions" in a native way.  There should be no surprise
that it is the only "container" (actually valarray is not a container
in the STL sense) that has such capabilities.  [Despite some weaknesses.]

[...]

| You can also see from the prototype above that my fft function takes a
| complex argument and returns complex values.  I have a function that
| transforms real data and returns complex values, too.  As long as both
| functions have the same prototype, then my code can transform both real &
| complex data.  I just always make sure to return complex values because,
| in general, the return value of an fft is complex, and you can't overload
| functions by return type.

If you offer and in-place implementation, then naturally you wouldn't
have to concern yourself with overloading on the return type.

| As far as handling integer or complex<int> input, it's certainly possible
| to pass in int or complex<int> arguments.

There is a portability issue here: pedantically, the effect of
instantiating std::complex<int> is unspecified (which means that the
implementation is not required to document what happens).

-- Gaby