[srean]

The discrete version of fast Fourier transform essentially does a matrix vector multiply faster than usual. If you are not familiar with matrix vector multiply, then think lots of multiplications and additions. Now, what fast Fourier transform does is take advantage of the fact xy + xz = x(y+z) that we know form mid school algebra. Note the right hand side has fewer operations to perform. The other thing that FFT uses is symmetry. It recognizes that two things that it needs to compute are really the same in value, so it computes it only once.

You can understand FFT without much deep math, it is just clever use of these two properties. Study it, you will really enjoy that cleverness. It is one of those algorithms that still makes me break out into a grin.

That said FFT can get more mathematically involved when you want to compute them on vectors whose lengths are not powers of two. Then it gets into primality, Chinese remainder theorem etc. However, for basic understanding and coding it you need none of these.

EDIT: I would say dont get lost in the details, those butterfly diagrams etc. Just focus on what is the key idea that it is exploiting. There are essentially just two ideas: ditributivity: xy + xz = x(y+z) and symmetry/associativity.

May be a good idea is to sit down and derive a different way to group the multiply and adds, using those properties, to make it go fast. Dont worry if that does not beat the best algorithms out there. You will just get a better feel for the underlying mechanism.

[coder23]

I did implement those, but the deeper understanding eludes me. Honestly I never gave them much though, when it comes to choose whether to take a week and learn it properly I always rather code or do something tangible. Except for linear algebra, which is something I might use in the future.