FHT vs FFT

From

Evgenij Masherov (2:5020/175.2)

To

Илья Кантор

Date

2002-10-28T21:21:10Z

Area

RU.ALGORITHMS

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

Mon Oct 28 2002 20:13, Илья Кантор wrote to Evgenij Masherov:

 
 EM>>>> В основном за счет того, что комплексное умножение это 4
 EM>>>> действительных  (+2 сложения), так что выгодно удвоить число
 EM>>>> умножений, если они  действительные.

 ИК>>> С другой стороны, комплексный вектор в 2 раза короче действительного ;)

 EM>> Совершенно верно. Вдвое больше вчетверо быстрейших. 

 ИК> Почему вчетверо ? Вдвое быстрейших. Что по cos+isin, что по cos+sin
 ИК> объединять - так и так умножений одинаковое количество будет.

 ИК> Наверное, эти самые 5% ускорения за счет сложений набегают.

c1=a1+b1*i
c2=a2+b2*i
c1*c2=(a1*a2-b1*b2)+(a1*b2+a2*b1)*i
4 умножения (и два сложения).
При расчете свертки и пр. - 4 умножения и 4 сложения.
В действительной же области
а*в - одно умножение (а свертка - умножение и сложение).
Операции в комплексной области вчетверо дороже каждая. 

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

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