The fast Fourier transform, developed by mathematicians John Tukey and James Cooley at Princeton University, is an algorithm for decomposing a time-based signal into its component frequencies far more cheaply than sending or processing the raw signal itself. It cut the computational cost of doing a Fourier transform from order n squared down to order n log n, a dramatic speedup for large datasets, and this made modern digital signal processing practical.
233 words · auto-generated from the episode video
27:07doing that is is is going to be quite expensive data wise because I've got to send all of that data, right? It would be really nice if we could decompose that time signal into a frequency. For example, you know, when I when I when I play a chord on a piano, one way to send all of that sound data is to send the microphone data. Or I could just send the notes that I played on the piano, the frequencies that I played. It's a way cheaper way of sending information. And in order to do that, you'd like to do a fora transform. Now, notoriously, this thing is extremely expensive to do computationally. um mathematicians John Tuki and James
27:48Kulie developed the fast 4year transform at Princeton University and they reduced that computational complexity to something that was totally manageable. Um the complexity went from order of n^ squ to n over login n login which is which is way lower like n squ goes like this n login kind of goes way way slower when it comes to like large n um and it launched modern digital signal processing. This is probably the most used algorithm in the entire world if I'm completely honest because no one's made a better way to do a 4A transform fast >> except for the guys at Pied Piper in
28:29Silicon Valley.