Отправлено Vadim Kudryavtsev 15 января 2005 г. 09:00 В ответ на: Ответ: И ПФ длиной равной, простому числу тоже можно сделать быстро() отправлено Vadim Kudryavtsev 15 января 2005 г. 08:55

Таким образом, так как ПФ длиной 5 раскладывается как 2х5х5, то нужно иметь процедуры ПФ длиной 2 (тривиально) и 5.
ПФ длиной 5 реализуется быстрым способом через короткую свертку.
Нет книжки под рукой к сожалению.
Найду - расскажу подробнее.

В результате алгоритм действительно получается менее эффективным чем 2^n, но все-же быстрый :-)

• Преобразование длины 50 - быстрая реализация (+) — Vadim Kudryavtsev   (17.01.2005 15:43, 2625 байт)