### Recursion Is Not Evil

Most of the known approaches to the FFT implementation are based on avoiding the natural FFT recursion, replacing it by loops. But a recursion is not expensive anymore, if it is resolved at compile-time, as it happens with template class recursion. Moreover, this kind of recursion can give performance benefits, since the code has been better unrolled than usual loops. This idea seems to be very similar to the approach of Todd Veldhuizen [6], who rewrote the same Cooley-Tukey algorithm (Listing One) completely in template metaprograms. The nested loops became recursive templates with nonlinear complexity, which can be compiled at most for `N=2`

on modern workstations taking much time and memory. Being quite efficient, this implementation has not been applied to real technical problems, because they often need to handle larger amounts of data. From these two points of view, I try to find a "golden section" using the efficiency of template metaprogramming and reducing compile-time to make the implementation applicable to huge signals limited only by physical memory.
^{{12}}

The approach presented here exploits the original recursive nature of the FFT implementing the Danielson-Lanczos relation (Example 2) using template class recursion. The necessary assumption is that the length of the signal `N=2`

is a static constant and is passed as template parameter ^{P}`P`

. I start in the high abstraction level dividing the algorithm from Listing One into two parts: the scrambling and the Danielson-Lanczos section. Listing Two represents the initial template class `GFFT`

with member function `fft(T* data)`

including two parts of the transform.

**Listing Two**

template<unsigned P, typename T=double> class GFFT { enum { N = 1<<P }; DanielsonLanczos<N,T> recursion; public: void fft(T* data) { scramble(data,N); recursion.apply(data); } };

The main point now is the implementation of `DanielsonLanczos`

template class using recursive templates, where `P`

is the power of 2 defining `N`

. Type `T`

is default type of the data elements. The implementation of the function `scramble`

will be mentioned briefly later and for now could be taken over from Listing One.

`DanielsonLanczos`

template class in Listing Three depends on the integer `N`

defining the current length of the data in the recursion and on the same type `T`

. To avoid the nonlinear number of instantiated templates, I define only one template class `DanielsonLanczos<N/2,T>`

per recursion level. Therefore, the total number of the template classes to be instantiated is `P`

+1. The constant `P`

can not be large because of the physical memory limits. For instance, if you have a data with complex elements of double precision (2x8 bytes per element), then `P`

may vary from 1 to 27 on a 32-bit platform. The case `P`

=28 corresponds to 4GB of data and there is no memory for some other program variables. `P`

can be bigger on 64-bit processors, but it's limited again by available physical memory. Such a number of the instantiated template classes should not provide any compilation problems.

The recursive idea of the Danielson-Lanczos relation is realized by two recursive calls of the member function `apply`

: the first time with the original signal data and the second time shifted by `N`

. Every next recursion level divides `N`

by 2. The last one is specialized for `N`

=1 and includes empty member function `apply`

.

**Listing Three**

template<unsigned N, typename T=double> class DanielsonLanczos { DanielsonLanczos<N/2,T> next; public: void apply(T* data) { next.apply(data); next.apply(data+N); T tempr,tempi,c,s; for (unsigned i=0; i<N; i+=2) { c = cos(i*M_PI/N); s = -sin(i*M_PI/N); tempr = data[i+N]*c - data[i+N+1]*s; tempi = data[i+N]*s + data[i+N+1]*c; data[i+N] = data[i]-tempr; data[i+N+1] = data[i+1]-tempi; data[i] += tempr; data[i+1] += tempi; } } }; template<typename T> class DanielsonLanczos<1,T> { public: void apply(T* data) { } };

After the recursion has been finished, the data is modified in the loop, where `cos`

and `sin`

functions used to compute the complex roots of unity (`c,s`

). The resulting `(tempr,tempi)`

is a temporary complex number to modify `(data[i+N],data[i+N+1])`

and `(data[i],data[i+1])`

. This simple implementation in Listing Three has poor performance due to many computations of trigonometric functions.