May 14 / David

Engine Difference Babbage’s

On my old blog, I once did a post on Babbage’s Difference Engine and how to run it backwards. However, I didn’t really finish the thought there and just recently it came up again IRL. 1 So this time, I think I’ll do the whole post.

The DE computed polynomials and worked by simple addition. It consisted of a series of numerical columns each of which had multiple digits, each column representing different stages of the computation, as I’ll show below. Suppose you have a function like

f(x) = x^2 + 1

I can compute this using only addition by starting with a table like this:

\begin{tabular}{ r r r r } $x$ & $f(x)$ & $f'(x)$ & $f''(x)$ \\ \hline 1 & 2 & 3 & 2 \\ 2 & 5 & 5 & 2 \\ 3 & 10 & 7 \\ 4 & 17 \end{tabular}

The x and f(x) columns are pretty self-explanatory. The f' and f'' columns are the differences between successive entries in the column to the left of each. For instance, the 3 at the top of the f' column is the difference between the 2 and the 5 in the f(x) column. The 2 at the top of the f'' column is the difference between the the 3 and the 5 in the f' column. (There are exactly two difference columns because this is a 2nd degree polynomial.)

Once I have a table started, I compute the function using simple addition from the right to the left, starting with the constant in the rightmost column, like this:

\begin{tabular}{ r r r r } $x$ & $f(x)$ & $f'(x)$ & $f''(x)$ \\ \hline 1 & 2 & 3 & 2 \\ 2 & 5 & 5 & 2 \\ 3 & 10 & 7 & \rightarrow \textbf{2}\\ 4 & 17 \end{tabular}

\begin{tabular}{ r r r r } $x$ & $f(x)$ & $f'(x)$ & $f''(x)$ \\ \hline 1 & 2 & 3 & 2 \\ 2 & 5 & 5 & 2 \\ 3 & 10 & 7 & 2\\ 4 & 17 & \rightarrow \textbf{9} \\ \end{tabular}

\begin{tabular}{ r r r r } $x$ & $f(x)$ & $f'(x)$ & $f''(x)$ \\ \hline 1 & 2 & 3 & 2 \\ 2 & 5 & 5 & 2 \\ 3 & 10 & 7 & 2\\ 4 & 17 & 9 \\ 5 & \rightarrow \textbf{26} \\ \end{tabular}

So all Babbage’s Difference Engine had to do was be able to add columns and it could compute tables of values for any polynomial (of degree n for some number of columns in his machine).

Not a lot of call for computing mathematical tables today and that goes double for mechanical computers. However, this technique can be used in reverse for something that’s slightly more helpful. Say I have a function that I can compute, but I don’t have a polynomial expression for it. I’m going to choose a simple one that probably has other ways to figure out:

\displaystyle{f(x) = \sum_1^x (k+1)}

Start by just computing a few values:

\begin{tabular}{ r r } $x$ & $f(x)$ \\ \hline 1 & 2 \\ 2 & 5 \\ 3 & 9 \\ 4 & 14 \\ \end{tabular}

Then the differences of those values

\begin{tabular}{ r r r } $x$ & $f(x)$ & $f'(x)$\\ \hline 1 & 2 & 3 \\ 2 & 5 & 4 \\ 3 & 9 & 5\\ 4 & 14 \\ \end{tabular}

Then the differences of those differences

\begin{tabular}{ r r r r } $x$ & $f(x)$ & $f'(x)$ & $f''(x)$ \\ \hline 1 & 2 & 3 & 1\\ 2 & 5 & 4 & 1\\ 3 & 9 & 5 \\ 4 & 14 \\ \end{tabular}

When the last column is constant, we are done and we know the degree of the polynomial we are looking for. 2 That polynomial can be expressed as

f(x) = ax^2 + bx + c

Which means the first differences column can be expressed as:

    \begin{eqnarray*} f'(x) & = & f(x+1) - f(x) \\ & = & \left[a(x+1)^2 + b(x+1) + c\right] - \left[ax^2 + bx + c\right] \\ & = & ax^2 + 2ax + a + bx + b +c - ax^2 - bx - c \\ & = & 2ax + a + b \end{eqnarray*}


Likewise, the second differences column can be expressed as:

    \begin{eqnarray*} f''(x) & = & f'(x+1) - f'(x) \\ & = & \left[2a(x+1) + a + b\right] - \left[2ax + a + b\right]\\ & = & 2a \end{eqnarray*}


This is the function for the last column, so now we know that in the searched-for polynomial a = \frac{1}{2}. With that, let’s back up a step and solve f'(x) using the known values of a, x and f'(x).

    \begin{eqnarray*} f'(x) & = & 2ax + a + b \\ f'(1) & = & 2(\frac{1}{2})(1) + (\frac{1}{2}) + b = 3 \\ b & = & \frac{3}{2} \end{eqnarray*}


And now do the same thing to solve for c.

    \begin{eqnarray*} f(x) & = & ax^2 + bx + c \\ f(1) & = & \frac{1}{2}(1)^2 + \frac{3}{2}(1) + c = 2 \\ c & = & 0 \end{eqnarray*}


So the final polynomial is

\displaystyle{\sum_1^x}(k+1) = f(x) = \frac{1}{2}x^2 + \frac{3}{2}x

And there we have it.

  1. Well, sort of. It was a math puzzle. ↩
  2. Actually, we only know it for the data we have. If this were a function in the domain of the reals, it could be doing anything between the points we selected. This is sort of a least-complexity polynomial for the given data. ↩
Filed under computers, math, mechanical
Leave a Comment

You must be logged in to post a comment.