Tag: Programming

The Yoda of Silicon Valley (Published 2018)

Donald Knuth, master of algorithms, reflects on 50 years of his opus-in-progress, “The Art of Computer Programming.”

Sometimes I don’t TLDR an article, because you should read it. (-:

Ken’s Take:

I’ve used his book(s) a lot. And recommend them frequently as well. I’ve not used TeX very much, but have dabbled (long ago) in LaTex, which is how most people use TeX. Now, though, I just let Word handle it.

What impresses me the most is the combination of doing amazing work but also being a humble, warm and happy person.

‘Life as we know it would be very different without the FFT.’

— Charles Van Loan

I’m not an expert in the Fast Fourier Transform (FFT). I first used it in 1985(ish) and have then used it in most decades since, including 2020. All facets of modern life are touched by the FFT, which is a fast way of doing a Discrete Fourier Transform (DFT), which is a non-continuous way to do the Fourier Transform (which most people learn in Differential Equations math course in college (if they learn it at all).

FFTs are generally used to turn time-series data (for instance a recording of your voice) into frequency domain (showing how much energy was in each frequency range measured in the sample). But that’s just the tip of the iceberg, and probably poorly explained!

My most recent use was to evaluate using certain characteristics of the FFT to replace expensive tensor convolutions in a convolutional neural network. It would have saved about 2/3rds of the convolution operations, which is terrific, except that in our particular network architecture the convolutions were a tiny fraction of the computational expense, so we opted for simple over perfect.

This article describes the FFT in one sentence… impressive! And this article is an overview of how it’s used.