Цитата(TigerSHARC @ Dec 20 2009, 15:59)

В литературе фигурируют несколько вариантов исполнения алгоритма БПФ:
Кули - Тьюки, Винограда, Блюштейна...
Есть ли практический смысл в анализе их реализации и конкретном выборе оптимального алгоритма для конкретной задачи.
Читаю у С.Смита, что все варианты БПФ дают приблизительно одинаковый выигрышь в производительности и, как я понял, особо заморачиваться нестоит...
(тем более, если честь что большинство библиотек для DSP написаны для Кули-Тьюки)
При программной реализации - да, если только не требуется по каким-то причинам конкретное N, а не ближайшее к нему 2**log(N)
При аппаратной реализации алгоритм Винограда может оказаться более выгодным за счет снижения кол-ва умножений, т.е. при нессиметричности затрат на сложение и умножение Кули-Тьюки не оптимален
Вот что говорится о конкретной реализации для "произвольного N"
http://forum.sources.ru/index.php?showtopic=273153&st=0* максимум быстродействия для степеней двойки; все дальнейшие случаи сравниваются с этим
* для N вида (2^i)*(3^j)*(5^k) - медленнее раза в полтора; впрочем, это отличие скорее всего будет уменьшено при помощи оптимизации
* для N с простыми множителями, большими пятерки, но значительно меньшими N, раза в три-четыре медленнее, но всё равно N*log(N); это уже не поддается оптимизации
* если само N - простое, то раз в шесть медленнее, но всё равно N*log(N); это тоже не поддается оптимизации
Алгоритм Томаса-Гуда для N составленого из взаимно простых множителей 2.3.5.7... не уступит Кули-Тьюки по быстродействию и структурно более прост. Но это неудобно, составлять N только из простых множителей