Цель статьи - не пренебрегая существенными аспектами алгоритмов, дать более-менее эффективные реализации. Если Вам необходима лишь эффективная процедура, выполняющая преобразование - в интернете их достаточное количество. В частности, очень хорошие результаты показывают пакеты "FFTW", и "T.Ooura FFT package".

Для понимания необходимо знание, что такое комплексные числа. Будут использоваться разные формы записи таких чисел, а также корни из единицы и их свойства.

Переопределения в исходниках:

typedef double          real;
typedef unsigned long   ulong;
typedef unsigned short  ushort;
typedef unsigned char   uchar;