Алгоритм ускоренного преобразования фурье на 2**N - 1 точек Опции

[Костян]

Подскажите, существует ли ускоренный алгоритм преобразования фурье на 2**N - 1 точек (например 255 или 511 точек) ?

[thermit]

Костян:
Так не получиться. Для линейной свертки бы подошло, а для циклической - нет.

Чудеса, да и только... И чего это подойдет для линейной, что не подойдет для циклической?

Код

  x=[-1 -5 4 9 -8];% длина 5
  y=[5 -9 8 4 -1 4 -6 -2 9 1 -5]; %длина 11
%Результат свертки x и y имеет длину 15
%Через FFT-15
  z=ifft(fft([x zeros(1,10)]).*fft([y zeros(1,4)]));
%Через FFT-16
zz=ifft(fft([x zeros(1,11)]).*fft([y zeros(1,5)]));

z=
1.0e+002 *

-0.050000000000000
-0.160000000000000
0.570000000000000
-0.350000000000000
-1.080000000000000
1.610000000000000
-0.460000000000000
0.070000000000000
0.210000000000000
-1.400000000000000
0.660000000000000
1.260000000000000
-0.830000000000000
-0.530000000000000
0.400000000000000

zz=
1.0e+002 *

-0.050000000000000
-0.160000000000000
0.570000000000000
-0.350000000000000
-1.080000000000000
1.610000000000000
-0.460000000000000
0.070000000000000
0.210000000000000
-1.400000000000000
0.660000000000000
1.260000000000000
-0.830000000000000
-0.530000000000000
0.400000000000000
-0.000000000000000 %Этот 0 выкидывается, потому как за пределами результата

Какие проблемы?

ps
Впрочем, если охота попреодолевать трудности - флаг в руки...