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:
Any feedback regarding GFFT project is greatly appreciated.
Please, write to: gfft (AT) scientificcpp (DOT) com
Last updated: |