Artifact 30aac07db1a49b69289dcfa47ac8a123493d0214

• File _lib/numeric/fft.cpp
  • 2011-02-23 09:21:16 - part of checkin [4fd800b3a8] on branch trunk - Copied from private svn repository. (user: kinaba) [annotate]
• File lib/numeric/fft.cpp
  • 2011-02-23 11:18:09 - part of checkin [23dfcca431] on branch trunk - renamed _lib to lib (user: kinaba) [annotate]

//-------------------------------------------------------------
// Fast Discrete Fourier Transform
//   O(n log n)
//   n must be a power of 2.
//
// Verified by
//   - SRM 436 LV3
//-------------------------------------------------------------

CMP tmp[65536*4];

template<int F>
void fft_impl( CMP a[], int n, int stride = 1 )
{
	if( n > 1 )
	{
		CMP *ev=a, *od=a+stride;
		int s2=stride*2, n2=n/2;

		fft_impl<F>( ev, n2, s2 );
		fft_impl<F>( od, n2, s2 );

		for(int i=0; i<n; ++i) tmp[i] = ev[s2*(i%n2)] + od[s2*(i%n2)]*polar(1.0, F*2*M_PI*i/n);
		for(int i=0; i<n; ++i) a[stride*i] = tmp[i];
	}
}

void fft( vector<CMP>& a )
{
	fft_impl<+1>(&a[0], a.size());
}

void ifft( vector<CMP>& a )
{
	fft_impl<-1>(&a[0], a.size());
	for(int i=0; i<a.size(); ++i)
		a[i] /= a.size();
}