Boost logo

Boost :

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

| 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

Boost list run by bdawes at, gregod at, cpdaniel at, john at