Микроконтроллеры

Ответ: Да, я сама лично писала процедуру FFT под пентиумный сопроцессор. Втиснулась в 8-регистровый стек, хотя для этого в одном месте пришлось прибегнуть к операции обмена значений между двумя элементами стека. Дополнительной памяти алгоритм не требует - преобразование происходит на месте самого преобразуемого массива. От величины преобразуемого массива потребление стека не зависит, функция получилась универсальная - длина массива не фиксирована, а задается параметром. Главное, только чтобы длина была кратна целой степени двойки. Основной алгоритм таков:

double w = M_PI;
for( int j = 1; j < N; j *= 2)
{ int j2 = 2*j;
  double x = 0;
  for( int k = 0; k < j; k++)
  { double cosx = cos(x), sinx = sin(x);
    for( int m = k; m < N; m += j2)
    { int l = m + j;
      double re = c[l] * cosx - s[l] * sinx;
      double im = c[l] * sinx + s[l] * cosx;
      c[l] = c[m] - re; c[m] += re;
      s[l] = s[m] - im; s[m] += im;
    }
    x += w;
  }
  w /= 2;
}

здесь массив c[] - действительная часть, s[] - мнимая часть числа. Или, соотвестввенно, коэффициенты cos и sin. Реальный же алгоритм несколько сложнее. Он включает битриверсивную процедуру и некоторые примочки. Среди примочек преобразование полностью действительного массива, без создания дополнительного с нулями (стандартные FFT поступают именно так, поскольку является комплекстным преобразованием). Идею я где-то позаимствовала, но код сочиняла сама, т.к. реализации не нашла.