19 #ifndef SNARK_MATH_FFT_H_
20 #define SNARK_MATH_FFT_H_
23 #include <boost/array.hpp>
33 template <
typename T, std::
size_t N >
34 void fft( boost::array< T, N >& data );
37 template <
typename T >
38 void fft( T* data, std::size_t size );
41 template <
typename T, std::
size_t N >
42 boost::array< T, N >
fft(
const boost::array< T, N >& data );
44 template <
typename T, std::
size_t N >
45 void fft( boost::array< T, N >& data )
50 template <
typename T, std::
size_t N >
51 inline boost::array< T, N >
fft(
const boost::array< T, N >& data )
53 boost::array< T, N > a = data;
58 template <
typename T >
59 inline void fft( T* data, std::size_t size )
61 unsigned long n, mmax, m, j, istep, i;
62 double wtemp, wr, wpr, wpi, wi, theta;
68 for( i = 1; i < n; i += 2 )
72 std::swap( data[ j - 1 ], data[ i - 1 ] );
73 std::swap( data[j], data[i]);
76 while( m >= 2 && j > m )
89 theta = -( 2 * M_PI / mmax );
90 wtemp = std::sin( 0.5 * theta );
91 wpr = -2.0 * wtemp * wtemp;
92 wpi = std::sin( theta );
95 for( m = 1; m < mmax; m += 2 )
97 for( i = m; i <= n; i += istep )
100 tempr = wr * data[j-1] - wi * data[j];
101 tempi = wr * data[j] + wi * data[j-1];
102 data[j-1] = data[i-1] - tempr;
103 data[j] = data[i] - tempi;
108 wr += wr * wpr - wi * wpi;
109 wi += wi * wpr + wtemp * wpi;
117 #endif // SNARK_MATH_FFT_H_