Forum Discussion

lori_m's avatar
lori_m
Iron Contributor
Feb 10, 2023

PeterBartholomew1 

Impressive FFT recursion! Interesting topic but unsurprisingly not a huge amount of feedback so far, perhaps tboulden might have further insight? I'd never used complex numbers in coding before and it didn't help that in the Rosetta Code link, the outputs from python as well as a number of other scripts were erroneous.

After a few false starts I ended up with the following representation for a complex matrix X+iY:

=LAMBDA(i,IF(i,X,Y))

I chose 'i' to indicate a complex number, though the 'i' is not imaginary here but a lambda parameter that may be input as (1), (0) or (({1,0}) for real, imaginary or both parts respectively.


I didn't manage to do the recursion but working through the referenced Wikipedia article was able to reduce the large DFT matrix multiplication into smaller matrix products. Even so, 4096 = 64x64 elements took just 0.1s compared to over 10s using the built-in Fourier analysis tool.

 

 

tboulden's avatar
tboulden
Iron Contributor
Feb 10, 2023

lori_m PeterBartholomew1 Apologies for my long absence! I'll have to dive-in on this over the weekend, but it looks pretty thrilling! Back once I've wrapped my head around it, or when I hit a brick wall and have a question!

  • lori_m's avatar
    lori_m
    Iron Contributor
    Feb 11, 2023

    Good to hear from you tboulden!

    I found this considerably mentally taxing too and that was without even attempting the recursion that Peter managed. Translating the equations into array operations was enough of an uphill climb in itself!

     

    I was pleased to be able to find the complex number representation above but found care was needed to maintain efficiency, particularly short-circuit evaluation of arguments via IF. I also wanted to add the python code did run successfully when I changed the output, I had just missed initially that the inconsistency was due to reporting amplitudes instead.

     

Resources