[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [List Home]
Subject: office-formula: FFT functions?
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.