The Algorithm That Made It Practical
Last timeThe Price of Looking for a Finite Time
The honest sum costs the square of the length. Splitting the readings into evens and odds turns it into two half transforms and one combining pass, and repeating that is the whole algorithm.
The transform was written down in the early eighteen hundreds. It became a tool
that engineers used daily in the nineteen sixties. The hundred and fifty years
in between were not spent on the mathematics, which was finished. They were
spent because nobody could afford to compute it.
A transform of a thousand readings asks a thousand questions and each question
looks at a thousand readings, so it costs a million products. A thousand
readings is about an eighth of a second of sound. Nothing about that is usable,
and the honest sum is the only thing on offer until somebody notices that the
sum repeats itself.
Where the work is being wasted
The direct transform fills in a square: every rate against every reading. In
each cell it computes a turn angle, multiplies the reading by it and adds the
result into that rate's total. The angles in that square are not a million
distinct numbers. The angle depends on the rate multiplied by the reading
position, so the cell for rate two and reading three holds the same angle as
the cell for rate three and reading two, and the same angle appears again at
rate six and reading one, and so on throughout.
Noticing that the angles repeat is not by itself enough; a table of angles saves
the trigonometry and still leaves a million multiplications and additions. The
useful version of the observation is structural. Because the angles repeat in a
pattern tied to even and odd positions, whole subtotals can be computed once and
used by several rates at the same time.
- the arrow for rate k of the whole list of N readings, which is what was wanted.
- the arrow for rate k of the readings at even positions, a transform of half the length. It is used by two different rates of the whole, which is where the saving comes from.
- one turn, by an angle that depends only on the rate and the length. This is the single multiplication per rate that joins the halves, and it is the only new arithmetic the splitting introduces.
- the arrow for rate k of the readings at odd positions, also a transform of half the length. Like the evens, it is reused rather than recomputed.
The split, done once and then again
The point of the identity is that it can be applied to itself. The evens are a
list of half the length, so split them into their own evens and odds. The same
for the odds. Keep going and the pieces get shorter by a factor of two each
time, until a piece holds a single reading, and the transform of a single
reading is that reading.
The lesson stops here
4 more paragraphs to go
You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.
The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.
See the planThe contentsThis is the reading half
Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.
The contents