🚀 go-pugleaf

Let me straighten things out here. It has been proven in several research
papers that the FHT transform always ALWAYS require N-2 (N-1 if N is odd) more
additions, but the same number of multiplications as the comparable FFT
algorithms (i.e. if compare a radix-4 FHT to a radix-4 FFT, a prime-factor FHT
to a prime-factor FFT etc). There exist a hybrid FHT/FFT algorithm, which
computes only requires 2 more additions for computing the FHT spectrum (same
number of multiplications), but it actually achieve the improvement from the
FFT. This statement holds true irrespective or the input data being real or
complex (yes the FHT can handle complex data).
For people interested in checking:
  The best length-N radix-2 Hartley transform for real input data requires
      3/4 * N log(N) - 5/2 * N + 4 multiplications
      7/4 * N log(N) - 5/2 * N + 4 addittions
		
and the best length-N radix-2 FFT for real input data requires
      3/4 * N log(N) - 5/2 * N + 4 multiplications
      7/4 * N log(N) - 7/2 * N + 6 additions

Exactly a difference of N-2 additions. As a matter of fact given a FHT
program, by removing an addition in one butterfly (which is executed N-2
times) and changing the input and output to the butterflies around a little,
one ends up with a FFT. And similarly a FFT can ealisy be converted into a FHT.

The FHT has only advantage over the FFT as far as I can see: The forward and
inverse FHT transforms are alike (except for the 1/N scaling factor) which is
not the case for the FFT.

Henrik Sorensen, Univ. of PA

******************************************************************************
*   Henrik Sorensen               Department of Electrical Enginering        *
*   Internet: hvs@ee.upenn.edu    University of Pennsylvania                 *
******************************************************************************