Overview

An algorithm is a recipe for doing computations. When children multiply two-digit numbers or "borrow" to subtract one number from another, they are using algorithms. More sophisticated algorithms enable computers to carry out computations that would otherwise be endless. The modern algorithm that has most transformed our society is the FFT (fast Fourier transform). "Whole industries are changed from slow to fast by this one idea which is pure mathematics," writes mathematician Gilbert Strang of the Massachusetts Institute of Technology [Strang, p. 290].

The FFT cuts from n ² to n log n the number of computations necessary to compute the Fourier transform of a signal with n values. (The logarithm base b of n, written log _b n, is the power to which one must raise the base b to obtain n: log ₂ 4 = 2, since 2 ² = 4; log ₂ 8 = 3, since 2 ³ = 8; log ₁₀ 100 = 2, since 10 ² = 100. In other words, log _b n is roughly the number of digits of n written in base b: log ₁₀ 1000 = 3; log ₁₀ 374113 ? 5.57; log ₁₀ 1000000 = 6.)

The bigger n is, the more impressive the gain in speed. If n = 2 ¹⁰ = 1024, then n ² = 1048576, while n log