Fast Fourier Transform
I wrote a java tuner app a few years ago, so I needed a Fast Fourier Transform to do the frequency detection. I found a fairly simple implementation in java on the web somewhere, can’t remember where, tried it, and it worked fine. The frequency detection algorithm comes from The Dsp Dimension.
A few years later I ported it to windows, added a few gizmos for tuning accordions and put it on Google Code. I was concerned that the FFT implementation was simplistic and did more research online to find better implementations. However, when I actually checked the performance with a profiling tool, I found that the spectrum display code was the bottleneck and the FFT was not significant. I tried a few different FFT implementations anyway, but they didn’t make a significant difference. I then ported the app to OSX, which has a built in high performance DSP library, so no problem there.
Later still, I ported it to Android, on GitHub, also on FDroid, and the FFT still worked fine in Java on Android. Then I had a request to add a spectrum display to my Oscilloscope app, also on FDroid. When I tried this on my Moto G phone, the spectrum obviously had a problem. When I checked, the problem was the simplistic FFT I have been using. So I did another web search and discovered FFTS, the allegedly Fastest Fourier Transform in the South. I couldn’t get this to build for Android using the script provided, so I did a fork on Github which I rearranged so it will build with the Android build tools. I also built a test app which does the tests shipped with the library. The FFTS library uses dynamic code which modifies itself, and also makes use of the ARM NEON engine if it is present. All three Android devices we have have NEON support in the processor.
I didn’t use this for the spectrum, the FFT buffer size was unnecessarily high, so reducing it solved the problem.