|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgenij Masherov 2:5020/175.2 28 Oct 2002 20:31:32
To : €«мп Љ в®а
Subject : FHT vs FFT
--------------------------------------------------------------------------------
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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
