Boost logo

Boost :

From: Jason D Schmidt (jd.schmidt_at_[hidden])
Date: 2002-09-22 19:55:49

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

 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
>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;

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

so I might as well make a copy at the same time and return it to make the
calling syntax a little more natural:

std::valarray<std::complex<value_type> > complex_data, ft_data;
// ... add data to complex_data
ft_data = fft<128>(complex_data);

>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

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.

>Did you consider to see how you may use
>pre-computed code paths with the algorithm that accepts dynamically
>sized input arrays?

I've glossed over the site briefly. I'm not sure what you mean by
"pre-computed code paths", but an algorithm for dynamically sized arrays
sounds very interesting. I'll take a look at it.

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

Think about this:

a = fft(b); // a is complex, b could be either real or complex
                      // easy to do, just overload the function

fft(b); // b could either real or complex
                     // however the ft of real input MUST be a real

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.

Thanks for your replies. I haven't had a chance to get any feedback on
this fft function until now, so I really appreciate these useful

Jason Schmidt

Juno offers FREE or PREMIUM Internet access for less!
Join Juno today! For your FREE software, visit:

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