FHT vs FFT

From

Илья Кантор (2:5020/175.2)

To

Evgenij Masherov

Date

2002-10-28T21:13:41Z

Area

RU.ALGORITHMS

From: "Илья Кантор" <ilia@manual.ru>

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

 ИК>>>> За счет чего такая экономия ?
 ИК>>>> Можно увидеть реализации алгоритмов FHT для действительных векторов
 ИК>>>> произвольной длины вида 2^k и для них же FFT ?

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

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

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

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

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

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