Блог пользователя armoking

Автор armoking, история, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • +77
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +33 Проголосовать: не нравится

    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?