This website appears broken in a very unique way on my iOS device. Whenever I swipe to scroll, the page gets zoomed out and it zooms back in when I stop swiping, but half of the content is cut off.
At the root of the fast transform is the simple fact that
ax + bx = (a+b)x
The right hand side has fewer arithmetic operations. It's about finding common factors and pushing parentheses in. Because of the inherent symmetry of the FT expression there are lots of opportunities for this optimization.
Efficient decoding of LDPC codes also use the same idea. LDPCs were quite a revolution (pun intended) in coding/information theory.
On the other hand, something completely random, few days ago I found out that Tukey (then a Prof) and Feynman (then a student) along with other students were so enamored and intrigued by flexagons that they had set up an informal committee to understand them. Unfortunately their technical report never got published because the war intervened.
Strangely, it does not find a mention in Surely You're Joking.
> At the root of the fast transform is the simple fact that
Actually... no? That's a constant factor optimization; the second expression has 75% the operations of the first. The FFT is algorithmically faster. It's O(N·log2(N)) in the number of samples instead of O(N²).
That property doesn't come from factorization per se, but from the fact that the factorization can be applied recursively by creatively ordering the terms.
The part about complex numbers needs some intuition to build. This comes up in linear algebra in very relevant ways too, for example in 3D computer graphics calculations.
This is just my 2 cents, but I don’t have an intuition built for complex numbers.
I have recently needed a decently performing FFT. Instead of doing Cooley-Tukey, I have realized the bruteforce version essentially computes two vector×matrix products, so I have interleaved and reshaped the matrices for sequential full-vector loads, and did bruteforce version with AVX1 and FMA3 intrinsics. Good enough for my use case of moderately sized FFT where matrices fit in L2 cache.
> I find they often use the phrase “fast Fourier transform” (or perhaps more often, the abbreviation “FFT”) when they mean “discrete Fourier transform” (or “DFT”).
12 comments
[ 3.1 ms ] story [ 47.2 ms ] threadEfficient decoding of LDPC codes also use the same idea. LDPCs were quite a revolution (pun intended) in coding/information theory.
On the other hand, something completely random, few days ago I found out that Tukey (then a Prof) and Feynman (then a student) along with other students were so enamored and intrigued by flexagons that they had set up an informal committee to understand them. Unfortunately their technical report never got published because the war intervened.
Strangely, it does not find a mention in Surely You're Joking.
Actually... no? That's a constant factor optimization; the second expression has 75% the operations of the first. The FFT is algorithmically faster. It's O(N·log2(N)) in the number of samples instead of O(N²).
That property doesn't come from factorization per se, but from the fact that the factorization can be applied recursively by creatively ordering the terms.
This is just my 2 cents, but I don’t have an intuition built for complex numbers.
Preach it, brother.