4 ms·
...FFT?
by TTPrograms 13y ago
...FFT?
- btilly 13y agoThe Fast Fourier Transform absolutely deserves to be on the list. All of signal processing went from, "We'd like to do a Fourier Transform but can't afford O(n^2) so here is a faster alternative that kind of does something useful" to, "We start with a FFT."
- tlarkworthy 13y agoyeah, bit biased towards CS. Neural nets opened a lot of doors. Bellman equation is in a lot of equipment.
- ArbitraryLimits 13y agoDijkstra's algorithm is close enough to the Bellman equation for programmers, I guess :) Also I don't really think taking a Taylor series for the inverse square root should count as an "algorithm."
- nly 13y agoI think the reason the inverse square root function got so much coverage was because of the bithacking of the float format, and the apparent WTFyness of the code. Also didn't it use Newtons method, not a Taylor series expansion? My math at that level is stale.
- NAFV_P 13y ago> ... and the apparent WTFyness of the code. That's what ID Software thought: http://en.wikipedia.org/wiki/Fast_inverse_square_root#Overview_of_the_code http://en.wikipedia.org/wiki/Fast_inverse_square_root#Overvi...
- sp332 13y agoIt did use Newton's method, and the cool part was that with a carefully-chosen initial value, you only had to run 1 iteration to get a reasonably good result.
- ArbitraryLimits 13y agoYou're right, it was Newton's method.
- GFK_of_xmaspast 13y agoIIRC, neural nets were a real backwater until recently when they figured out to train them effectively.
- tlarkworthy 13y agonot true. ANNs were one of the first general purpose functions. Once people got their heads round ANNs properly they got generalised to kernel methods. So now modern machine learning often don't look like neural nets anymore, but the lineage from back propagation is obvious. Deep belief nets have made things that look like neural nets popular again, but things like sparse ICA stacks is suggestive of another wave of theory led morphing back to non-neural architecture. But the point is that the theory followed after the invention of neural architectures both times. So the root is the ANN, and thus I think it is a really important algorithm in history. It was a bio inspired innovation too which is interesting.
- mjcohen 13y agoWhich seems to have been invented by Gauss.
- fla 13y agoAnd Reed-Solomon error correction.