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

"VelociChicken" <bob@[EMAIL PROTECTED]
> wrote in message 
news:Nf5Lk.160694$ix.59555@[EMAIL PROTECTED]
> >The same savings can be obtained for an FFT algorithm specialized for
>>real inputs.
>>
>>Yes, if you have an FFT subroutine that takes n complex inputs and
>>returns n complex outputs, then you would need to take your real
>>inputs and convert them into a complex array with zero imaginary
>>parts, requiring twice the storage.  However, it's been observed since
>>(I think?) the late 1960's that this factor of 2 is not necessary.
>>
>>Instead, there are a number of FFT algorithms specialized for real
>>data that take a real array as input, and return half of a complex
>>array as output (requiring the same storage as the real array, and
>>possibly operating in-place).  The reason you can do this is that the
>>discrete Fourier transform of real inputs is half redundant: the
>>second half is the complex conjugate of the first half, in reverse
>>order.
>>
>>(Probably the most well-known such technique, although not generally
>>the most efficient, is a trick to express a real-input DFT of length n
>>in terms of a complex-input FFT of length n/2 plus some post-
>>processing.   An alternative technique is to start with a complex-data
>>FFT algorithm, and go through the algorithm and prune out the
>>redundant operations...again, you can save a factor of 2 in memory and
>>slightly more than a factor of 2 in computation compared to the
>>complex-input algorithm.)
>>
>>The existence of these real-input FFT algorithms is why all claims of
>>factor-of-two savings from FHT algorithms were (at best!) very
>>misleading, as was pointed out shortly after FHTs was introduced.
>>Inexplicably, this mythical factor of two has persisted for an
>>amazingly long time in the imaginations of engineers (and some
>>unfortunate authors).
>>
>>Regards,
>>Steven G. Johnson
>
> Thank-you for your verbose and interesting reply. Is it possible to tell

> me which would actually be the best (fastest, and free) real-FFT that I 
> can test myself? I'm using Intel CPUs.
> Thanks again,
> Dave

These graphs appear to show FHT in good favour:

http://www.geocities.com/ResearchTriangle/8869/fft_summary.html

Does anybody agree? I'm guessing the trig table and accuracy tradeoffs
have 
a big part to play in the results.