FHT vs FFT

From

Evgenij Masherov (2:5020/175.2)

To

Илья Кантор

Date

2002-10-28T16:11:16Z

Area

RU.ALGORITHMS

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

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

 EM>>  Преобразование Хартли весьма похоже на преобразование Фурье и может
 EM>> быть  рассмотрено, как вычислительная схема для расчета Фурье. В нем
 EM>> вместо  синуса и косинуса в качестве базисных функций используется
 EM>> cas(x)=cos(x)+sin(x). Как следствие, все вычисления делаются в
 EM>> действительной арифметике, но с вдвое бОльшим числом коэффициентов, что
 EM>> в  целом дает двукратную экономию даже по сравнению с вариантом Фурье,
 EM>> оптимизированным для действительных чисел.

 ИК> Очень интересно ! За счет чего такое ? Кучу программ смотрел для
 ИК> вычисления пи (профессиональные программы, мировые рекорды пи и т.п.),
 ИК> там оптимизированные FHT и FFT дают примерно один и тот же результат.
 ИК> Хотя, в общем и целом, для быстрого умножения FHT быстрее где-то на 5%

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

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

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

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