
Boost : 
From: Gabriel Dos Reis (gdr_at_[hidden])
Date: 20020922 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 "inplace". 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 npoint fft, the first thing that has to be done is
 to calculate the bitreversal of the indices (it's the critical part of
 the algorithm). The bitreversed indices are different for each
 different fft size. With my code, a 128point fft is a different
 function from a 256point function (because the size is a template
 parameter).
If you're only offering a compiletime size, then it may worth
calculating also the bitreverse array at compiletime 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
precomputed 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 containergeneric 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
"arrayexpressions" 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 inplace 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk