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.
rigtorp 14 minutes ago [-]
How is belief propagation used for decoding LDPC codes related to FFT?
connorboyle 13 minutes ago [-]
Author here: thanks for sharing!
terabytest 4 hours ago [-]
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.
bonefolder 4 hours ago [-]
Quite funny because now I can’t access the comment box at all.
f1shy 4 hours ago [-]
Same here. I think is intended as “feature” but extremely annoying.
sunrunner 3 hours ago [-]
I'm struggling to imagine what the feature is intended to be. Being able to see a larger portion of the page while scrolling? This...doesn't help at all, sadly.
2 hours ago [-]
Mikhail_K 1 hours ago [-]
Fast Fourier transform was not invented by Cooley-Tukey,
it was used by Gauss to compute trigonometric interpolation of orbits from observations.
srean 28 minutes ago [-]
True. Before Fourier did Fourier.
ajross 45 minutes ago [-]
The factorization trick was reinvented several times. The algorithm that uses it to do a frequency decomposition was presented just once by named authors. This happens all the time. Freaking out about naming and attribution isn't really very informative.
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.
Edit: as always, Wikipedia is a better source than comment pedantry: https://en.wikipedia.org/wiki/Fast_Fourier_transform#History