_______ __ _______
| | |.---.-..----.| |--..-----..----. | | |.-----..--.--.--..-----.
| || _ || __|| < | -__|| _| | || -__|| | | ||__ --|
|___|___||___._||____||__|__||_____||__| |__|____||_____||________||_____|
on Gopher (inofficial)
URI Visit Hacker News on the Web
COMMENT PAGE FOR:
URI Fast Fourier Transforms Part 1: Cooley-Tukey
Mikhail_K wrote 28 min ago:
Fast Fourier transform was not invented by Cooley-Tukey,
it was used by Gauss to compute trigonometric interpolation of orbits
from observations.
ajross wrote 1 min 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.
srean wrote 1 hour 38 min ago:
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.
DIR <- back to front page