armoking's blog

Fast Hartley Transform and Fast Fourier Transform
By armoking, history, 4 years ago, In English

Hello everyone, today I learned the fast Hartley transform and solved a problem with it. In my opinion, this algorithm is very similar to the FFT, but it does not use any complex numbers. So my question is — if this algorithm is easier to implement than the FFT, then why is the first one not as common as the Fourier transform?

And one more — if you have a better implementation (I think, it is easy), please share it in the comments.

Thanks

  • Vote: I like it
  • +77
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

The code you have shared seems to be identical to FFT. In the name of not using complex numbers, it is just unrolling $$$\cos x + i\sin x$$$ into two different numbers. Everything else seems to be exactly as in FFT. In FFT you multiply two complex numbers, and here you are just unrolling the multiplication.

I don't see why you think this algorithm is easier to implement than the FFT. If anything, FHT brings in extra trouble.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

    I think and yes and no, This algo is really looks like default fft, but in the implementation of the fft we have an array of complex numbers arr, but here we use only one array of doubles.

    Btw, what do you mean in "extra troubles"? For now, I have find that the only problem of this algorithm is impossibility of modular calculations (may be it is wrong). Are there any other problems?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -12 Vote: I do not like it

      I mean implementation wise, FFT should be easier and faster to code.

      → Reply