Forum Discussion
Would you recommend the use of Excel complex numbers where performance is required?
That is some impressive coding for Excel formulas. Sorry I missed your original post. Do you actually work with FFTs or was it just a case of experimentation with modern Excel?
I found the theoretical basis of the FFT algorithm somewhat heavy-going and finished up by implementing version with a double recursion. I am now looking at following
Nonrecursive Fast Fourier Transform - YouTube
to see what a non-recursive form might look like.
As for the original question on the in-built complex function calculation, your answer is very much in line with my expectations. Thanks for the confirmation.
I needed the FFT for a fast convolution of probability distributions. I had previously used a VBA implementation, and recently migrated to pure Excel formulas. It is at least as fast as the VBA implementation, except for some edge case when copying formulas to a different sheet (relevant thread here: https://techcommunity.microsoft.com/t5/excel/puzzling-performance-issues-with-lambda-array-formulas/m-p/3720783).
How do you plan to make a non-recursive version? Implementations in "fast" languages such as C use arrays that are mutated in place. Have you found a way to emulate that in Excel?
Basically I used REDUCE for applying both the even-odd sort matrix and the butterfly matrix. Any judgement of how Excel handles that iteration/recursion would be pure guesswork on my part. At the more detailed level, I transformed the part-processed result as each stage so that the blocks of the right-hand side vector were stacked horizontally and then the multiplication by a block diagonal matrix reduced to a single broadcast product.
For me, the DFT wasn't something I needed. The exercise, rather like the fourth order Runge-Kutta routine I wrote, were tasks conducted to see how far I could get with spreadsheet formulas and the extent to which they could replace VBA or other formal programming languages. I am interested that you have a real application that has driven your development to such a level. I had planned to complete the work by implementing the inverse version of the formula and then, maybe applying it to some convolution problems.
I have (finally) achieved another Excel formulation of the Cooley-Tukey Decimation in Time (DIT) method for the implementation of the Discrete Fourier Transformation. The core of the implementation is to use new array shaping functions to allow multiplications involving partitioned matrices to be carried out as simple array products using broadcasting.
I am getting to think of the manipulation and presentation of 2D arrays as the core functionality of any spreadsheet. What TOCOL and WRAPCOLS achieve, is to arrange any multidimensional dataset so that one dimension represents the array operation whilst the other represents a stacking of the remaining dimensions which allows the operator to act on a 'for each element' basis.
Modern Excel is pretty good at this now, provided the array operation itself results in a scalar value; for the majority of problems one is somewhat screwed (to use a technical phrase or saying that needs to be quoted with caution). I for one am getting to be irritated by the number of times I have to resort the REDUCE/VSTACK when I really meant to use SCAN, BYCOL, MAP, which whine about nested arrays, when the sole purpose of the entire calculation was to deliver as set of nested arrays!
Fortunately this particular workbook was an exception, in that one of the dimensions was always devoted to real/imaginary parts and even I can manage arrays of size two, without resorting to full-blown array algebra!
- Some further information for the record. The spreadsheet ran with 64K rows, taking 2360ms. More realistic was the 20ms for 1K growing linearly to 80ms for 8K rows. Far more usable than I had anticipated!
