I over-engineered a Fast Fourier Transform for Arduino
There’s an alternate way to save space: the discrete Hartley transform.<p><a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=27386319" rel="nofollow">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=27386319</a><p><a href="https:&#x2F;&#x2F;twitter.com&#x2F;theshawwn&#x2F;status&#x2F;1400383554673065984" rel="nofollow">https:&#x2F;&#x2F;twitter.com&#x2F;theshawwn&#x2F;status&#x2F;1400383554673065984</a><p><pre><code>  dht(x) = fft( (1 + 1j)*x ).real &#x2F; area(x)**0.5

  area(x) = np.prod(np.shape(x))
</code></pre>
The dht is its own inverse, which is a neat trick. No need for an inverse fft. In other words, dht(dht(x)) == x.<p>Notice that the output is the real component of the fft. That means the storage required is exactly identical to the input signal. And since the input signal is copied to the real and imaginary components (1 + 1j)*x, the intermediate representation size is also equal to the input signal size. (Just take sin and cos of the input signal.)<p>The dht has almost all the same properties of the fft. You can blur an image by taking a hamming window and multiplying. You can resize an image by fftshift + pad with zeros + fftshift. Etc.<p>In practice the dht seems to have all the benefits of fft with very few downsides. I’m amazed it isn’t more popular.