Overview

GFFT is generic simple and efficient Fast Fourier Transforms (FFT) implementation using policy-driven design and template metaprogramming.

The key idea is to assume the transform length N be a compile-time static constant. This assumption makes possible to implement natural recursion and some compile-time calculations needed for FFT such as computation of roots of unity. They are based on the compile-time integer computations. Due to trigonometric functions evaluation at compile-time, the first step in FFT computation usually known as "planning" becomes unnecessary. Additionally, C++ compiler can utilize compile-time static constant for better optimization. The latter fact has been proved in first benchmark tests that have shown surprising and significant performance improvements comparing to Cooley-Tukey algorithm implemented in C.

Not only the transform length N, but also other options and transform types are defined as template parameters too. This allowed to apply fascinating techniques of policy-driven design (from the book "Modern C++ design" by A. Alexandrescu). The resulted C++ program components are short, highly reusable and flexible, while compiled code stays fast and efficient, because all the template parameters are resolved during compilation into optimized code.

Further details to the ideas behind this project have been published online in the article "A Simple and Efficient FFT Implementation in C++". by Dr. Dobb's journal.

Basic features of GFFT:


Contact

Any feedback regarding GFFT project is greatly appreciated.
Please, write to: gfft (AT) scientificcpp (DOT) com


Last updated: