A few days ago I posted a ooBasic script that can be used in LibreOffice to do a Discrete Fourier Transform (DFT) on a set of cells. While it works, it is slow. This is because the a raw implementation of a discrete Fourier transform runs at a complexity of O( n2 ). That is, the number of operations required to compute is the square of the number of data points. Since this grows exponentially, slightly larger data sets take significantly longer to compute.
Naturally, the solution is to switch to a Fast Fourier Transform (FFT). These can generally reduce the complexity down to O( n log2 n ). I knew this when implementing a DFT, but implementing an FFT is a bit more complected. ooBasic kinda...well, pretty much sucks as a programing language. So to do an FFT implementation I wanted an algorithm fairly straight forward to translate. I surveyed several libraries but ultimately decided on Free small FFT. It included a fairly clean radix-2 Cooley–Tukey FFT algorithm but also had Bluestein's algorithm for data not in powers-of-two. The complexity looks to be something around:
I am judging this based on the fact it does three radix-2 transforms on a four times the rounded up power-of-two.
Why does anyone need an FFT in a spreadsheet? I’m not the only person who has searched for such a function, but the primary reason I want one is to do a spectrum plot of a sampled signal. It doesn’t happen often that I need one, but when I want it, I want it in the spreadsheet and would rather not have to go to an external tool.
Today I finished making a simple project page to host the script. Installing it in LibreOffice isn’t easy, but the steps outline in the manual section seem to work. They don’t make it easy, but should anyone else ever want LibreOffice Calc to do an FFT, this should work.