On Thu, 16 Oct 2008 16:48:44 -0700 (PDT), "Steven G. Johnson"
<stevenj@[EMAIL PROTECTED]
> wrote:
>On Oct 16, 4:19 pm, Eric Jacobsen <eric.jacob...@[EMAIL PROTECTED]
> wrote:
>> Again, it's a bit more complicated than just counting how much memory
>> is needed. How it's used can make a big difference, too. Since
>> the FHT can directly take the real-valued input buffer in the time
>> order in which it is presented, there can be an advantage depending
>> (again) on the implementation and what you're trying to do. The same
>> is true on the output, the same is true in the way that the twiddle
>> tables are used.
>
>If you are implying that the FHT operates on in-order input and
>output, while a real-data FFT cannot, then you're wrong.
>
>> Things like incrementing a pointer into a memory is easier (and
>> typically faster) than manipulating an address via a computation. That
>> can make a significant difference and isn't reflected by just
>> analyzing memory sizes.
>
>Of course, but there's no significant difference between FHTs and real-
>data FFTs in this regard. (This has been pointed out again and again
>in the literature on the subject, dating back to the late 1980s.)
>
>However, since you feel so strongly to the contrary, I look forward to
>your pointing out an FHT implementation that beats the best known real-
>data FFT implementation by a significant margin for any modern CPU.
>I'm sure that such an FHT implementation will see widespread use once
>its performance has been demonstrated, and for my own part I try to
>keep abreast of the latest developments in the field.
Dude, chill. I've no dog in this hunt, I'm merely pointing out that,
just like with most things, there are some subtleties where one may
have an advantage over the other given particular constraints. Is
that so surprising? They're not identical, you know.
>> And optimizing transforms for computation on a CPU is only relevant to
>> comparisons on that CPU. I'm looking at it far more generically, as
>> the sorts of applications where the difference may matter may not be
>> run on a CPU or DSP at all.
>
>If you're going to distance yourself from readily available computers
>where your claims can be tested, there's not much to talk about.
>
>Steven
And, as has been recognized here multiple times, if one wants to run
on "available computers" and use such canned solutions, then that's
the environment for comparison in that case. In the real world,
however, things often get implemented on various platforms (processors
or in hardware) that fit the application or just what's available at
the time. In those conditions, one plays the tradeoffs to the
resources that they have available, and that may not include canned
optimized solutions or even various ingredients (e.g., FIFOs) that
could make the job easier.
Unless you want to claim that an FFT always provides a superior
implementation op****tunity compared to an FHT under all possible
cir***stances I don't think there's an argument here. Even if you do
want to claim that my response will just be, "More power to ya." The
differences are small and subtle and I don't think worth the effort in
the majority of the cases. As I stated very early in the thread, for
the vast majority of cases these days memory and processing power are
inexpensive and readily available to the point that just plugging in a
canned FFT (super efficient or not) is clearly the way to go. If one
has to split hairs it's usually more productive to improve
efficiencies elsewhere rather than spend the time to redevelop a
canned block like an FFT, but, nevertheless, sometimes it does get
down to that.
There are times when an obscure tool or technique can provide an
advantage. Being aware of the obscure tools and the differences
allows that to be part of the tradeoff space.
Eric Jacobsen
Minister of Algorithms
Abineau Communications
http://www.ericjacobsen.org
Blog: http://www.dsprelated.com/blogs-1/hf/Eric_Jacobsen.php
|
