office-formula: FFT functions?

["Steven G. Johnson" <stevenj@fftw.org>]

Hi, I was wondering if there was any interest in including a discrete 
Fourier transform function in OpenFormula (and, based on that, one can 
easily implement convolutions, correlations, autocorrelations, etcetera as 
desired). e.g. Excel has some FFT functionality via the data analysis 
toolpack, as I understand it, but I didn't see anything in the OpenFormula 
draft.

I'm co-author of FFTW (www.fftw.org), a popular free-software FFT 
implementation (used e.g. in Matlab, GNU Octave, etc.), and I wanted to 
send you a note in case you wanted any help with this.  I would be happy 
to provide any advice on specification, a reference implementation, 
etcetera that you might need.  I'm not a spreadsheet expert, but I hope 
that my knowledge of FFTs and their applications would be helpful.

We get a sizeable amount of email at fftw.org from people who just want to 
transform some data in a spreadsheet, and so I get the impression that 
that there is a fair demand for this kind of capability; also, if you 
google "excel fft" you will get a lot of pages.  FFTs themselves are kind 
of hard for a user to implement in a spreadsheet language, but once you 
have them there are all sorts of things that can be done directly in the 
formula language (windowing, filtering, correlations, etcetera).

Regards,
Steven G. Johnson [stevenj at math dot mit dot edu]

PS. If you do specify FFT functions, you don't want to make the same 
mistakes that Excel did, e.g. you don't want to artificially limit support 
to power-of-two sizes (a very inconvenient restriction for analysis of 
user-generated data).  Given a power-of-two FFT, you can implement support 
for arbitrary sizes with a couple dozen more lines of code (via 
Bluestein's algorithm), so there's really no excuse not to support any 
size with O(n log n) complexity.