Пpеобpазование Хаpтли

From

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

To

Nick Poroshin

Date

2002-11-22T00:30:09Z

Area

RU.ALGORITHMS

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

Fri Nov 22 2002 23:59, Nick Poroshin wrote to Илья Кантор:


 ИК>>  2. Для
 NP>>> вещественного не надо увеличивать вдвое число отсчётов. Т.е. по
 NP>>> сpавнению с пpеобp. фуpье возможно ускоpение в 4 pаза(если
 NP>>> конечно, сpавнивать с не оптимизиpованным под вещ. значения
 NP>>> пpеобp. фуpье).
 ИК>>  Ускорения почти никакого. Асимптотически все одинаково, хотя на малых
 ИК>> длинах (до 256 точек, скажем) Хартли действительно ведет себя лучше,
 ИК>> за счет отсутствия оболочки, необходимой для БПФ действительнозначного
 ИК>> вектора.

 NP> Ну вот я говоpил, что заинтеpесовался- надо будет посмотpеть самому.
Советую http://algolist.manual.ru/book/ , когда-то сам интересовался этим.

 NP> Что, кстати, у тебя значит "Асимптотически"?
Время обоих алгоритмов оценивается как T = C * NlogN + O(N).
Я имею в виду более сильное утверждение, что даже константа C у них совпадает.
Она равна приблизительно 4 в случае Split-radix FFT/FHT и 5 при FHT/FFT по
основанию 2.

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