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.