From: Jason D Schmidt (jd.schmidt_at_[hidden])
Date: 2002-09-22 19:55:49
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:
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 http://www.fftw.org/ 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
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
GET INTERNET ACCESS FROM JUNO!
Juno offers FREE or PREMIUM Internet access for less!
Join Juno today! For your FREE software, visit:
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk