October 26, 2020

Charles Babbage and the method finite differences

Charles Babbage and the method finite differences

It's the 1800s and you find yourself arguing with strangers over the telegraph. A heated debate takes place as you cannot agree on what's a good approximation for the natural logarithm of forty-two.

As you type out harsh sequences of stern morse-encoded words with one hand, you hold the latest, hottest edition of a table of logarithms on the other. There is just no way you are wrong. Not this time. Still, you decide to check the disputed value in another book. And then in another. Oh, crap.

Back in the day, human computers would spend uncountable hours multiplying and adding numbers for approximating logarithms and trigonometric functions. The process was very fragile: in calculating, compiling the results and typesetting for printing, errors would frequently slip through the cracks and make it to the final table. It is not hard to understand why people listened with interest when, in 1822, British mathematician Charles Babbage announced his newest invention could automatically spit out error-free numerical tables by the turn of a crank.

Babbage, the now celebrated inventor of the computer, designed the difference engine, a mechanical calculator built for magically tabulating polynomials. Equipped with intricate combinations of gears and rotors, the original design required over 25,000 parts - later reduced to 8,000. The groundbreaking machine was capable of performing additions in the context of the method of finite differences.

You swallow your pride and calm yourself down with teaspoon of a cough syrup you recently grew oddly fond of. It's mostly morphine. "This Babbage character is on to something", you think.

The method of finite differences

At the heart of Babbage's machine, the method of finite differences provides the theoretical steps for tabulating polynomials using only additions. The method's goal is to tabulate values of a polynomial p(x) for many values of x. To make matters concrete, let's illustrate the method with the particular instance p(x) = x^2 + 4x - 5, a randomly picked second-degree polynomial.

While the whole point of the method is to produce values of p(x), let's pretend for a second that we already have the values of p(x) for some values of x, just so we can observe an interesting property of polynomials:

x	p(x)
0	-5
1	0
2	7
3	16
4	27
...	...
Table 1. Values of x and p(x)

Here is where the fun begins. We add a new column whose values are computed from the existing table. The values in the new column, diff1, are calculated by subtracting two neighboring values from the column on its left: diff1(x) = p(x + 1) - p(x):

x	p(x)	diff1(x)
0	-5	5
1	0	7
2	7	9
3	16	11
4	27	13
...	...	...
Table 2. Make sure you understand how diff1 is computed

The process is then repeated, recursively. We add a second column, diff2, whose values are computed from the existing column on its left (diff1), in the exact same fashion as before: diff2(x) = diff1(x + 1) - diff1(x):

x	p(x)	diff1(x)	diff2(x)
0	-5	5	2
1	0	7	2
2	7	9	2
3	16	11	2
4	27	13	2
...	...	...	...
Table 3. Final table with diff1 and diff2

"That's odd", you think. Values in the newest column, diff2(x), always equal 2. You might try the same process for other second degree polynomials. diff2(x) is constant, every single time. In fact, that is a fundamental property of finite differences that makes Babbage's machine possible: for a polynomial of degree N, the column diffN(x) will always be constant (see exercise 3).

Visually, if we take a closer look somewhere in the middle of the table we created, this is the generalized relationship we see:

...	diffK(x)	diffK+1(x)	...
...	...	...	...
...	a	c	...
...	b	...	...
..	...	...	...
Table 4. Visual representation of related cells in terms of a, b, c

The relationship c = b - a is precisely the equation we used for generating the values in columns diff1 and diff2. Moreover, the relationship extends to the p(x) column, which we can effectively treat as column diff0(x).

How the method of finite differences works

Here comes the kicker. Flip this relationship on its head, so we have b = c + a. Now look again at the visual relationship between a, b and c in table 4. Intuitively, this means that, were the values of a given row known, the whole row below it could be computed using nothing but addition operations. And then, recursively, the row below that one could be computed and so on, until the whole table magically materializes itself. I invite you to manually try this process for a few rows using a copy of this spreadsheet we put together, starting from the empty cell in the upper right corner. Check your results against the table above.

This is the crux of how Babbage's difference engine works. A human operator calculates the first row of the table manually and loads these values by means of setting up the initial positions of the machine's rotors. Then, by turning the crank, additions are recursively performed until the values of p(x) (or, equivalently, diff0(x)) are produced. It is wonderful and mesmerizing to watch this process happen, and you can see it in this video of a difference engine (built only in 2008!) from the Computer History Museum in California.

Tabulating functions other than polynomials

The method of finite differences works for polynomials, but what about non-polynomial functions like log(x)? Luckily, mathematicians have had a neat trick under their sleeves since the early 18th century. The Taylor series expansion was then an already known method for finding a polynomial approximation for suitable functions. The catch is that the original function has to be well behaved when differentiated multiple times. Luckily again, many trigonometric, logarithm and exponential functions fit the bill perfectly.

In the coding challenge below, we will employ a 7th-degree Taylor polynomial approximation for sin(x) and tabulate its values via the method of finite differences, as would the difference engine. If you're ready for a good time, step into Babbage's shoes and let's party. 1822 style.

Programming exercise

We will now investigate how Babbage's difference engine works for approximating a trigonometric function. The goal of this coding challenge is to tabulate the function sin(x) for x = {0.0, 0.01, 0.02, 0.03, ... 1.0} using the method of finite differences.

As explained above, we first need to find a polynomial approximation for sin(x). To kick things off, we put together a 7th degree Taylor polynomial approximation for sin(x) as well as the values for the first row of the table - you can find it in this spreadsheet. The values in this precomputed first row (highlighted in green) are the ones that would be manually loaded into the difference engine at the beginning of the tabulation process. Similarly, for us, these values will be input for the computer programs we will write here.

1. There is a concise and elegant recursive relationship for calculating the value of the p(x) in the row r, given some values of the row immediate above it. In your favorite programming language, write a recursive function that returns the value of p(x) in the row r (r is the input of this function).

   • What is the big-Oh time complexity of your solution in terms of the polynomial degree and number of rows in the table?
   • What is the big-Oh space complexity of your solution in terms of the polynomial degree and number of rows in the table? Don't forget to account for the call stack space.

2. The naïve recursive function above is beautiful, but unfortunately prohibitively slow for large tables. Implement a solution that works for large tables.

   • What is the big-Oh time complexity of your solution in terms of the polynomial degree and number of rows in the table?
   • What is the big-Oh space complexity of your solution in terms of the polynomial degree and number of rows in the table?

3. We claimed that, for a polynomial of degree N, the column diffN(x) will always hold a constant value. Sketch a proof of this claim for N = 2.

If you are stuck, we have a few hints for each exercise. Do not hesitate to get in touch - it's always a pleasure.

More resources

• The Babbage Engine at the Computer History Museum.
• The analytical engine, a programmable mechanical computer later also designed by Babbage, takes the ideas behind the difference engine to the limit. Even though never fully realized in practice, it has many similarities to modern computers - parts than can be oddly accurately mapped to modern-day CPUs, registers, arithmetic logic unit (ALUs). This is the machine computer pioneer Ada Lovelace is known for having written the first computer program for.
• Babbage's Analytical Engine video by Computerphile on YouTube.