The Difference Engine - not just a cool book.

I think the first time I read about the Difference Engine was actually in the novel of the same name by William Gibson and Bruce Sterling. The book is an alternative history, set in the 19th centuary where Charles Babbage, actually finished building the Difference Engine, a Mechanical calculator he designed. This in turn lead to him getting funding for the Analytical Engine, a Turing-complete mechanical computer which Babbage also designed in real life, but also didn't actually finish building. I really enjoyed the book, but how plausible was this chain of events? How did the Difference Engine work? And what problem was Babbage trying to solve when he came up with the idea for the Difference Engine?

Computers before Computers

Before electronic computers were invented, scientist and engineers were forced to use various tricks and short cuts to enable them to carry out difficult calculations by hand.  One short cut that was used extensively, and one which Babbage would have been very familiar with, was the use of log tables to speed up multiplication. A log tables is simply a table which lists the values of the logarithmic function. If like me you've never used a log table, then how are they useful?

Log Tables

The property of logarithms that makes them useful in simplifying certain calculations is that:

$ log(AB) = log(A) + log(B) $

We use this property often in number theory when we wish to turn a multiplicative problem in to an arithmetic problem and vice versa. In this case it's more straightforward though. If we want to calculate $A*B$ we can convert the figures into logs, and then we just need to add the logs together and convert back to obtain the value of $A*B$.

Lets say we want to calculate $ 134.7 * 253.9 $ . What we can do instead is calculate:

$ log( 134.7) = 2.1294 $ and $ log (253.9) = 2.4047 $

then we just need to add together​

​​​$ 2.1294 + 2.4047 = 4.5341 $

and convert back from logs

​​​$ 10^{4.5340} = 34200 $

which we can easily verify as the number we require. 

Haven't we just made our problem even harder though? Before we needed to multiply two numbers, and now instead we need to do two conversions and an addition, admittedly it's easier to add two large numbers together than multiply them, but what about the conversion? The way around this is to have a book of the values of the log function so that we can just look up the log of any number we are interested in, allowing us to easily convert to and from logs.

This is probably a good point to introduce Charles Babbage properly, Babbage was an English Mathematician, Inventor, and Philosopher born in 1791. He was a rather strange guy, as well as making important contributions to Computer Science, Mathematics and Economics, Babbage founded multiple societies. One society was founded to investigate paranormal activity, one was founded to promote the use of Leibniz notation in calculus, and another was founded in an attempt to foster support for the banning of organ grinders.
​
When he wasn't keeping himself busy investigating the supernatural, Babbage was also a keen astronomer. Since astronomy is computation heavy, this meant that Babbage was forced to make extensive use of the log tables that were available at the time. These tables had all been calculated by hand by people called computers. Being a computer was a legitimate job at one point, they would sit and carry out calculations by hand all day every day, not the most exciting job if you ask me. Because the log tables had all been created by teams of human calculators, errors had naturally crept in. The tables were also very expensive to produce. This lead Babbage to conceive of a mechanical machine for calculating log tables, he called this invention the Difference Engine.

Method of differences

A difference engine uses the method of finite differences to calculate the integer values of polynomial functions. I remember noticing something similar to the method of finite differences when I was playing around trying to guess the formulas for sequences of integers at school. 

If someone gives you an integer sequence and they ask you to find the formula, say we are given,

$1,4,7,10,13,...$

Then, in this case, the answer is easy, we can see that we are just adding 3 each time. To make this completely obvious, we can write in the differences between the numbers..

1 - 4 - 7 - 10 - 13 - ...
  3    3    3    3

What if we are given a slightly more complex sequence though? For example:

$1,3,6,10,15,...$

This one is a bit more complicated, let's see what happens when we add in the differences again:

1 - 3 - 6 - 10 - 15
  2    3    4     5

Now we see that there is an obvious pattern in the number we are adding on each time. Looking at the differences between these numbers we see:

1 - 3 - 6 - 10 - 15
  2    3    4     5
      1    1    1

So what's happened here? We now have stability on the second level of the differences. It turns out that this is equivalent to the underlying formula being a quadratic. In this case the formula is $0.5*x^2+1.5x+1$. If we assume the first number in the sequence is equivalent to $x=0$ we can now easily recreate the sequence, and easily calculate the next value.

Let's try a difficult example, if we are given the following sequence and told to guess the next value, we can use a similar method to get the answer.

$2,5,18,47,98,177$

Setting up the method:

2 - 5 - 18 - 47 - 98 - 177
   3   13   29    51    79
     10  16    22    28
         6    6     6

Since we get a constant at the third level, this sequence must be a cubic, once we know this, it's much easier to guess what the actual formula is. In this case it is x^3-x^2-x+3. Babbage's insight was that we can calculate the next value in this sequence just by adding on another diagonal to this table of differences.

Adding $6$ to $28$ gives $34$, then adding $34$ to $79$ gives $113$, and then adding $113$ to $177$ gives us $290$. Which means that the next value in the sequence is $290$ So we get:

2 - 5 - 18 - 47 - 98 - 177 -  290
   3   13   29    51    79    113
     10  16   22    28    34
         6    6    6       6

As you might guess, this process generalises to higher order polynomials. For a given sequence, if we keep trying the differences of the differences and eventually get to a constant then we will know the sequence is formed by a polynomial, and we will also know the degree of the polynomial. So if you are ever a given an integer sequence and asked to find the pattern, always check the differences and see if it eventually becomes a constant, if it does, then you will know the order of the polynomial which defines the sequence and you will also be able to easily compute the next value directly.

So how does this apply to Babbage's difference engine?

The insight is that we have here a method of enumerating the integer values of a polynomial just using addition. Also at each stage we only need to store the values of the leading diagonal. And each polynomial is uniquely determined by specifying its differences.

The underlying message is that multiplication is difficult. In order to come up with a shortcut for multiplication, we use log tables to make the problem additive. And even further, we now have a method for calculating the log function which also avoids multiplication.

So given we have this method of calculating the integer values of a polynomial, how can we use this to calculate values of the log function?

​Approximating Functions

The obvious way to approximate a log function with a polynomial would be to just take its Taylor expansion.

For example, the Taylor expansion of $ log ( 1 - x ) $ is:

$ log ( 1 - x ) =  - \sum^{\infty}_{n=1} \frac{x^n}n $

There is a downside to using the Taylor expansion though. Given the mechanical constraints at the time, Babbagge's Difference Engine could only simulate a 7th degree polynomial. So how close can we get with a Taylor expansion? We can use Taylor's theorem to calculate the convergence of the approximation, but this will be quite a bit of work, and since we can easily calculate the actual value of the log function it's easier to just test the approximation with a computer. So taking $log(0.5)$ as an example, when I use a calculator, I am told that it equals $-0.6931$, but when I check the 7th order polynomial I get $-0.6923$, and it's not until I get to the 10th polynomial that we are accurate even to 4 digits.
​
If we require a more accurate approximation, we will have to use numerical methods in conjunction with a restriction on the range of convergence. This would mean that if we wished to compute $log(x)$ on the interval [0,1], for 100 different points on the interval, we would break [0,1] into sub-intervals and then use a different polynomial fit for each sub-interval.
​
If you'd like to read more about how the actual machine worked then the Wikipedia is really useful.
en.wikipedia.org/wiki/Difference_engine

And if you are interested in reading more about the mathematics behind using a Difference Engine then the following website is really good:
ed-thelen.org/bab/bab-intro.html