Не помню подробно - возможно, где-то ошибаюсь (!!!)
(года 4 назад разбирался)

Примерно это выглядит так :
(более подробно можно прочитать у Уолт Кестер, Глава 5, Быстрое преобразование Фурье)

Есть входной массив - 4 выборки (int in_x[4];)
Считаем реальную и мнимую компонеты (long ReX; long ImX;)
Для расчёта необходимы таблицы синусов и косинусов, на которые надо домножать.
Но ! Если взять 4 выборки со сдвигом 90 градусов - эти массивы вырождаются в нули и единицы (-1; 0 +1...)
Т.е. ни то, что плавающая или фиксированная точка - даже умножение не требуется - только сложение int в long.
Формально (без выкидывания умножения) :
void calc_g()
{
unsigned char i;
ReX=0;
ImX=0;
for (i=0;i<NNN;i++)
{
ReX+= in_x[i]*cos_t[i];
ImX+= in_x[i]*sin_t[i];
}
}

Далее, получаем амлитуду и фазу :

int amp()
{
return (ReX*ReX +ImX*ImX); //или корень из этого - не помню
}

int phase()
{
return arctan(ImX/ReX);
}