Пpеобpазование Хаpтли

From

Evgenij Masherov (2:5020/175.2)

To

Илья Кантор

Date

2002-11-20T21:27:36Z

Area

RU.ALGORITHMS

From: "Evgenij Masherov" <EMasherow@nsi.ru>

Wed Nov 20 2002 21:21, Илья Кантор wrote to Evgenij Masherov:

 EM>> Оно, собственно, и определено для того, чтобы не возиться с
 EM>> комплексными.  Но реальный выигрыш не более чем двукратный.

 ИК> За счет чего он 2кратный может получится ? Вроде, говорили уже об этом..
 ИК> Могу перепостить сообщение с оценками, хотя на твоем сайте я его вижу..

Двукратный выигрыш получается из того, что БПФ по К точкам может быть
применено для вычисления действительного преобразования Фурье по 2К точках.
Оно же может быть вычислено при помощи БПФ по 2К точкам.
Число элементарных операций для Фурье составляет C*(K*log K)+O(), для Хартли
C*(2*K*log(2*K))+O(). Однако комплексное умножение-сложение требует вчетверо
больше операций, чем действительное, что и дает (пренебрегая разницей между
логарифмом К и 2*К) примерно двойной выигрыш.
Что и подтверждается моим скромным практическим опытом.

Евгений Машеров АКА СанитарЖеня

--- ifmail v.2.15dev5
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)