[boost] fft

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

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

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

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
discussions.

Jason Schmidt

________________________________________________________________
GET INTERNET ACCESS FROM JUNO!
Juno offers FREE or PREMIUM Internet access for less!
Join Juno today!  For your FREE software, visit:
http://dl.www.juno.com/get/web/.