Re: "Discrete Hartley transform" vs " Discrete Fouuier transform"

On Oct 13, 10:53=A0am, "VelociChicken" <b...@[EMAIL PROTECTED]
> wrote:
> Despite the arguments on theory, I found FHT to be 50% faster than any
FF=
T
> code on the internet, so I use it. It's probably the cos/sin
approximatio=
ns
> and that it uses half the memory, which helps the data cache and prep
tim=
e.

If so, you're using the wrong FFT implementation (or you have an
amazing FHT implementation that you have not yet revealed to the
world).  I've benchmarked a lot of FHT implementations, and I'm not
aware of any that comes close to the fastest optimized real-data
FFTs.  (Especially since most FHT implemenations are of the textbook
radix-2 variety.)

As I mentioned above, there is negligible theoretical advantage one
way or the other between FHTs and real-data FFTs so far as anyone
knows (the best known real-data FFTs are actually slightly better from
an arithmetic-count perspective), so it comes down to
implementations.  And people have spent far more effort optimizing FFT
code than they have in optimizing FHT code.  (e.g. every CPU vendor
has an optimized FFT for their chip, usually including a real-data
FFT; I can't think of a single recent general-purpose CPU vendor that
has released an optimized FHT.)

Steven