Re: [boost] fft

From: Gabriel Dos Reis (gdr_at_[hidden])
Date: 2002-09-23 04:38:15

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

| Excerpts from 
| Date: 22 Sep 2002 10:02:42 +0200
| From: Gabriel Dos Reis <gdr_at_[hidden]>
| In-Reply-To: Jason D Schmidt's message of "Sat, 21 Sep 2002 17:48:25
| -0600"
| 
|  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.
| 
| Actually, the computation is actually done in-place; here's how:
| 
| std::valarray<value_type> bit_reversed_data(data.size());
| bit_reversed_data[bit_reversed_indices] = data;
| 

That is not what is called "in-place transformation".  In-place
transformation means the input-array contains the result of
transformation:  bit-reversal and butterflies are applied to input
array.

| Then the in-place "butterfly" computation is applied to
| bit_reversed_data.  If I didn't copy the data, I'd still have to apply
| the bit-reversal the same way:
| 
| data[bit_reversed_indices] = data;        // still making a copy;
| probably no speed gain

The speed gain is in when you return the result -- that is why I was
referring to the NRVO.

[...]

| >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.
| 
| I'll have to think about how to do that.  Not using a std::valarray
| object would not allow me to apply the bit-reversal the same way (as
| demonstrated above).  Also, I'm not sure users of the fft function would
| see much further speed benefit.

If you do a 1024-length transform with precomputed bit-reverse, I as a
user (doing polynomial multiplication) *can see* a speed benefit :-)

[...]

| I think the most common use of the ft is to transform real data, which
| returns a complex result (in general).  It would severely handicap the
| fft function to disallow that.  If I'm missing something here, please let
| me know.

I think your assesment that the most common use isn't in-place
tranform isn't accurate.  Maple, since loooong time ago, has been
offering an in-place transform.  That is the transform used in its
signal processing toobox.
(As an FFT user I certainly prefered and implemented the in-place
transform while back when working on polynomial solver).

You can easily build a non-in-place transform on top of an in-place
one than the contrary, so I would suggest to provide a function for
the in-place transform.

-- Gaby