FHT vs FFT

From

Evgenij Masherov (2:5020/175.2)

To

Илья Кантор

Date

2002-10-28T19:31:32Z

Area

RU.ALGORITHMS

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

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

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

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

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

Совершенно верно. Вдвое больше вчетверо быстрейших. Примерно вдвое выигрыш.
Тут еще интересно обсудить, как на сравнительную эффективность программ влияет
изменение времени выполнения операций. Скажем, в пособиях до 70-х годов
включительно зачастую считалось не общее число операций, а только умножения. А
теперь эти операции примерно равны (или - точно равны) по времени.

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

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