OASIS Mailing List ArchivesView the OASIS mailing list archive below
or browse/search using MarkMail.


Help: OASIS Mailing Lists Help | MarkMail Help

office-comment message

[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [List Home]

Subject: Add FFT() to formula spec?

Hi - We've received a proposal to add a Fast Fourier Transform (FFT) function to the OpenFormula spec.  The proposal itself is from Steven G. Johnson; Rob Weir wrote a public reply to it.

What does everyone think?  Pro? Con? Don't care?  I don't think this should be required for small or medium; heck, it doesn't even need to be included in a group at all.  Details below.

Arguments for it: Excel has an FFT in a data pack; FFT is common in engineering.  By spec'ing it, we increase portability in this area.
Arguments against it: Many spreadsheets don't have it, or have it as a standalone function; most spreadsheet users don't know or care what it is.  Implementations can add their own functions like FFT, they don't need OpenFormula's permission to do so.

In college I wrote a paper comparing parallel FFT implementations, and like most electronics engineers I've used FFTs.  So I'm quite aware that FFTs have many users.  I'm inclined to say "yes, if the proposer writes the initial spec, and isn't required for small or medium".  But I'd like to hear what others think.

--- David A. Wheeler 

----- Start Original Message -----
> From: "Steven G. Johnson" stevenj, at, fftw.org
> 01/28/2008 05:58 PM
> Please respond to stevenj, at, math.mit.edu
> To  office-comment at, lists.oasis-open.org
> Subject [office-comment] 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.
> This publicly archived list offers a means to provide input to the
> OASIS Open Document Format for Office Applications (OpenDocument) TC.
> In order to verify user consent to the Feedback License terms and
> to minimize spam in the list archive, subscription is required
> before posting.

Robert Weir replied:
> Hi Steven,
> This is an interesting idea.  In practice,do you think this makes sense as 
> spreadsheet array functions which take an array and return an array?  Or 
> as an application comment that prompts the user to select an input and 
> output range,along the lines of what Excel does with its Analysis Toolkit?
> My experience is that most users are not even aware of array functions in 
> Excel and how they use.  On the other hand, most users are not aware of 
> FFT's either.
> If done as a spreadsheet function, the FFT would obviously need to be 
> recalculated every time one of the cells in the input range changed.  At 
> O(N log N) this isn't so bad.
> Do you know if there are any ways to calculate an FFT with incremental 
> changes?  So I calculate once in O(N log N) and then change only some of 
> the input cells, a small portion of them -- is there a much faster way of 
> calculating the new results?
> Note also that complex number support in spreadsheets is rather poor in 
> general, and only a handful of functions work with them.
> What functions would you recommend?  Maybe FFT() and the inverse IFFT(). 
> Each one might have a parameter that specifies the normalization 
> convention.  Maybe also a Power() function?  I could imagine in the time 
> domain CrossCorrelation()and AutoCorrelation() would be useful as well. 
> These are interesting for fields beyond signal processing, including 
> economics.
> Note however that it is always a debatable point on whether a particular 
> feature request should be placed in the standard, or whether it is best 
> done as an extension.  I'd be more encouraged to add features like this to 
> the ODF standard if we had one or more vendors committed to supporting 
> this feature in their product. 
> If it were purely up to me, I'd love to create the ultimate 
> engineer's/scientist's spreadsheet application.   There are a lot of 
> things we could do, like adding units support, integration with R, etc. 
> But we would need a set of volunteers dedicated to implementing this in 
> OpenOffice or Gnumeric or someplace.
> Regards,
> -Rob
> ___________________________
> Rob Weir
> Software Architect
> Workplace, Portal and Collaboration Software
> IBM Software Group
> email: robert_weir, at.., us.ibm.com
> phone: 1-978-399-7122
> blog: http://www.robweir.com/blog/

----- End Original Message -----

[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [List Home]