Method of Differences

2024-02-02

The “Method of Differences” is a mathematical technique for reducing the computation of polynomials to repeated addition. Once the system is setup, relatively unskilled human computers can populate dense mathematical tables. This is the “difference” in the Charles Babbage’s Difference Engine which aimed to automate the creation and printing of these tables. I have created a playground where you can experiment with the method and in this article I aim to explain how to apply the technique, why the Difference Engine earned public funding, and the limitations of the method.

Try it yourself: Method of Differences Playground

How it works

In his 1822 letter, Charles Babbage states that using the engine that he has just finished, he has constructed tables of square numbers: $x^2$, triangular numbers: $x^2/2 + x/2$, and the expression $x^2 + x + 41$.

Let’s use the example $x^2 + x + 41$.

Since the example is already a polynomial, we can compute the Initial Values. The highest power of the polynomial is 2, so we need 3 (2 + 1) rows. First, we’ll compute the expression at x=0 and two steps using standard methods:

$x$	$f(x)$
0	41
1	43
2	47

Because the highest power of the polynomial is 2, there are two difference ($D$) columns we need to compute. We will append the two columns to the right of the table:

$x$	$f(x)$	$D^1$	$D^2$
0	41
1	43
2	47

Then, using simple differences, we will compute the $D^1$ column by subtracting values in the left-same $f(x)$ and left-below columns:

$x$	$f(x)$	$D^1$
0	41	43 - 41 = 2
1	43	47 - 43 = 4
2	47

Recursively, we will then do the same for $D^2$. If there were more difference columns, the process would be repeated.

$x$	$f(x)$	$D^1$	$D^2$
0	41	2	4 - 2 = 2
1	43	4
2	47

The first row of this table becomes our Initial Values: 41, 2, 2.

Now, to compute the function, we can use repeated addition. We initialize the table with the Initial Values like so:

$x$	$f(x)$	$D^1$	$D^2$
0	41	2	2

Then, cells equal the cell above plus the cell to the above right. The last column on the right will stay constant.

$x$	$f(x)$	$D^1$	$D^2$
0	41	2	2
1	41 + 2 = 43	2 + 2 = 4	2

Append another row:

$x$	$f(x)$	$D^1$	$D^2$
0	41	2	2
1	43	4	2
2	43 + 4 = 47	4 + 2 = 6	2

Repeating the process, the table becomes:

$x$	$f(x)$	$D^1$	$D^2$
0	41	2	2
1	43	4	2
2	47	6	2
3	53	8	2
4	61	10	2

Non-Polynomials

If your expression is not a polynomial, it may be possible to convert it to one or approximate it as a polynomial. For example, using Taylor series, $sin(x)$ can be approximated as:

$$\frac{x^9}{362880} - \frac{x^7}{5040} + \frac{x^5}{120} - \frac{x^3}{6} + x$$

Once in a polynomial form, you can use Method of Differences to compute a table of values. However, as an approximation, will contain errors and, as the number of rows builds, the error will increase.

Playground Syntax

The Method of Differences Playground parses expressions using SymPy.

The expression requires and permits only a single variable: x.

Exponents are expressed with double asterisks, i.e. x**4 means raise x to the 4th power.

As of the date of this post, logarithms are not supported. Trigonometric functions are supported.

Why did people care?

Mathematical tables were deeply important for both practical and academic reasons. Looking up a value was far faster and less error prone than calculating a value from scratch. Francis Bailey, later head of the Royal Astronomical Society, presented a long list of mathematical tables which were amenable to this technique:

Examples	Examples	Examples
Products of numbers	Square numbers	Cube numbers
Higher powers	Square and cube roots	Reciprocals
Sine, Cosine, Tangent	Logarithms	Logarithmic sine, cosine, tangent, cotangent
Hyperbolic logarithm	Astronomical	Navigation

Populating the tables was tedious work, but since it was just repeated addition, it was amenable for computers. At this time, a computer was a human that did calculations. If you were starting a new project, you would hire a number of computers and set them on the same task, in parallel. The project lead could then check the outputs of the computers against each other, which was a fair way to establish reliability. Since errors in addition would have additive error in the output, binary search would be an effective checking technique. At the end, the tables would be copied over to the publisher, at which case the editor would need to perform additional checks for correctness.

As you can see, the process still allows many avenues for errors as well as requiring significant intellectual labor. Babbage’s Difference Engine promised to eliminate the intellectual labor by replacing the human computers and eliminate the copying errors by producing the tables automatically. These two elements together were considered necessary by Babbage and he argued against separating the computation from printing, even though that might have led to an earlier deliverable.

Beyond the immediate practical aspects, the rapid and inexpensive production of tables would encourage the exploration of new mathematical functions. For example, interpreting polar coordinates is much aided by tables of trigonometric functions. For a deeper discussion on the context of the Difference Engine, see Doron D. Swade’s article Calculating Engines: Machines, mathematics, and misconceptions in Mathematics in Victorian Britain.

**Update 2024-02-20: I’ve described additional applications of the method.

Limitations

Since many functions, including all the trigonometric and logarithmic functions, can only be approximated by polynomials, method of differences will produce errors in the output. Not all errors are fatal, though. For example, a B.H. Babbage documents, the Engine was to use 20 places of figures and handle six orders of differences. Many errors could be minor, and so by truncating the answer to fewer digits, the answers would be correct. Mathematically, one could also re-center tables on new initial values, which could eliminate accumulated errors in previous rows.

While method of differences is a useful technique for generating tables, it is not general-purpose. One can’t use it to interpolate a value using Newton’s Method, determine if a number is prime, tabulate a census, or choose different tax rates based on a category. The Analytical Engine (theoretically) could, which is why its potential value was so greater.

\(x\)	\(f(x)\)	\(D^1\)	\(D^2\)
0	41
1	43
2	47

\(x\)	\(f(x)\)	\(D^1\)	\(D^2\)
0	41	2	2
1	41 + 2 = 43	2 + 2 = 4	2