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