Last week John W. Tukey died; he was 85 years old. Tukey was a Princeton professor, ostensibly a statistician, who coined the words "software" and "bit". He rediscovered and popularized the Fast Fourier Transform ("FFT"), a hack worth knowing both for its beauty and its utility.
Fourier Transforms (FTs) map information from one space to another. The best examples are from the world of music. Consider, for starters, a note — a single pure tone. On the one hand, it's an oscillating pressure wave in the air, a wiggle on an oscilloscope or phonograph record groove, a sequence of numbers stored on a CD or in a computer's memory. That's the tone in the time domain. But the same information can also be represented as a note on the musical scale: a static description of the frequency and amplitude and phase, essentially timeless. "Play me an A440." That's the tone in the frequency domain.
FTs are magical mathematical transporters that take data back and forth between frequency and time universes. They work for complex chords and sequences, the same way that an orchestra can turn sheet music into a symphony (and, inversely, a Mozart can hear a performance and write it down). FTs also work on images (think holograms), on quantum mechanical particles (think wavefunctions), on interstellar signals (think radio astronomy), on voices (think digital cellphones), and on a host of other things. FTs are vital for signal processing, noise reduction, and efficient information transmission.
But FTs are also horrendously expensive to compute — or rather, they used to be, pre-Tukey, pre-FFT. Take 1,000 numbers, perhaps representing 0.1 second of ordinary speech. To Fourier Transform them by the obvious method takes about 1,000 * 1,000 * 1,000 operations = a billion multiplications and additions. That's marginally possible, today, with fancy computers. But it's not cheap, it doesn't fit into a handset, and it doesn't scale. The computational cost gets worse like the cube of the number of samples that have to be processed.
But there's a better way. Mathematicians discovered that the FT process was full of regular patterns and could be decomposed into simpler sub-steps. The 1,000 by 1,000 FT matrix of a million numbers can be factored into 10 pieces — 10 clever sparse matrices that multiply together to give the original FT, but that each are mostly full of zeroes. (Multiplying by zero is easy!) A billion operations collapse into only ~10,000. And the factoring trick scales up; it grows slowly, like N*log(N) instead of exploding like N cubed. A million numbers can be transformed in ~20 million operations instead of 1,000,000,000,000,000,000 (1018). Amazing savings!
That's the Fast Fourier Transform, aka FFT. Dedicated mathematicians figured it out, published it in their obscure journals, and moved on to prove other theorems. A few decades later Tukey and colleagues rediscovered the FFT and realized how valuable it might be — with the newly-developed programmable digital computers to do the arithmetic. The rest, as they say, is history.
John Tukey did many things besides uncovering the FFT. I was lucky enough to meet him ca. 1990 and showed him some of my work on user interfaces for free text information retrieval — key parts of which he had anticipated and implemented 30 years earlier! (See KwicsChinksAndChunks", the ^zhurnal entry of 31 January 2000, for the story of the JWT-^z encounter. See also FreeTextDesiderata and http://www.his.com/~z/ftirp.html ,"FTIR Philosophy", for more about the subject, and consult the Free Text archive at http://www.his.com/~z/c/ for annotated C source code, compiled executables, and implementation examples.)
John W. Tukey — creative, helpful person. Requiescat in Pace.
Monday, July 31, 2000 at 05:55:32 (EDT) = 2000-07-31
TopicProfiles - TopicScience - TopicPersonalHistory - TopicProgramming
(correlates: KwicsChinksAndChunks, AirFlow, TripleThrills, ...)