1 A first look at differencing

When in 1821 the English mathematician Charles Babbage invented what we now recognise as the grandfather of the modern computer he called it the 'Difference Engine' since it was intended to take over the work of making mathematical tables by the techniques described in this article. 

Image				Image
Photo courtesy of the Charles Babbage Institute, University of Minnesota, Minneapolis.				Reproduced by courtesy of IBM Computer Museum.

n0123456789n²0149162536496481

If we want to know 5² we simply look at the entry under 5.

Exercise 1 Produce a similar table of cubes.

Mathematicians found a large number of tricks to make the construction and use of tables easier. Here is one of them. Consider our table of squares. Let us take the difference between successive entries as shown below.

Now take the difference of successive differences to obtain

Finally we take the difference of the differences of the differences to obtain

Let us try the same thing on a table of 4th powers.

This time successive differencing produces the following table.

Exercise 2 (i) Extend the table of 4th powers n⁴ to cover n=8 and n=9. Verify that the pattern suggested above continues to hold.

(ii) Find the effect of repeated differencing on your table of cubes.

Exercise 3 (i) Try the effect of repeated differencing on 3n³ -5n² .

(ii) Try the effect of repeated differencing on a polynomial of your choice.

It very much looks as though the effect of repeated differencing a polynomial of degree m is to produce a row of zeros after at most m+1 differences. Let us try our conjecture on the most general quadratic f(n)=An² +Bn+C. Here is part of the initial table

and here are the repeated differences

Image

Since we could pick any k to investigate, we have verified the conjecture for the general quadratic.

Exercise 4 Verify the conjecture for the general cubic.

The next exercise requires more algebra.

Exercise 5 (i) If f(n)=n^k show that f(n+1)-f(n) is a polynomial in n of degree k-1.

(ii) If g(n) is a polynomial of degree k show that g(n+1)-g(n) is a polynomial in n of degree k-1.

(iii) Prove our conjecture that the effect of repeated differencing a polynomial of degree m is to produce a row of zeros after at most m+1 differences.

We now observe that we can reconstruct the whole of a table of differences for a polynomial from a small part of it. For example, suppose we are told that f is a quadratic polynomial and its table of differences looks like

We can immediately fill in the last but one row to obtain

and then the next to obtain

Exercise 6 (i) Fill in the top row and check that we have the table of n² -n+1 with the leftmost entry corresponding to n=0.

(ii) Fill in in the following table of differences for a quadratic.

Check that the table you get is for f(n)=3n² -5n-3 with the leftmost entry corresponding to n=0.

Now suppose that we want to tabulate f(n)=n³ -3n² +5n+1. Here is a partial tabulation which the reader should check.

We can now draw up a partial table of differences which the reader should check.

But we can now reconstruct the full table of differences. Here is a partial reconstruction

Notice that we have extended our original table to read

Exercise 7 Continue the reconstruction of the table of differences to the point where you have the value of f(n) for n=-4, n=4 and n=5. Check your answers by computing f(-4), f(4) and f(5) directly from the definition.

Exercise 8

Let $f(n)=3n^2+2n+1$. Compute f(n) for n=-2, -1, 0, 1, 2. Form the associated partial table of differences and then reconstruct the table of differences sufficiently far that you have f(n) for all n with $-5\leq n\leq 4$. Check your answer by computing f(n) directly.

The fact that (at least for polynomials) we can use differences to reconstruct a full table from a partial table gives a strong hint as to why table makers were so interested in these ideas.

Here is another reason. Suppose we have a table like the following.

in which all the entries are zero except one. If we compute successive differences we get

Exercise 9 (i) Calculate one further row of differences.

(ii) Conjecture the form of the nth row of differences.

(iii) [Harder and optional] Prove your conjecture.

Exercise 10 (i) Find the successive differences for the table

(ii) Find the successive differences for

(iii) Find the successive differences for

(iv) Suppose f is a cubic polynomial. What is the fifth line in the table of successive difference for f? Find the fifth line of the table of successive differences whose first line is

Explain how you can find A just by looking at the 5th line.

(v) The following table is supposed to represent the values of a quadratic but I have made a mistake in one entry.

By successive differencing find the error and correct it.

(vi) Explain how you can locate and correct a single error in a table of a polynomial of degree k.

(vii) Explain how you would try to locate and correct a single error in a table of a polynomial whose degree you did not know.

Successive differencing thus gives an excellent way of finding and correcting errors in tables.

2 A second look at differencing

So far we have only looked at tables of a function f as a method of finding f(n) where n is an integer. However we really want to know f(x) at all points x. In other words, knowing f(0), f(1),..., f(m) we want to find f(x). We shall see that this can be done but we will need to raise the mathematical level a little bit.

The key is a set of observations which go back at least as far as Newton.

Exercise 11 (i) Consider the function f₂ (x)=x(x-1)/2!. We tabulate it as follows.

Find the table of successive differences.

(ii) Do the same for f₃ (x)=x(x-1)(x-2)/3!, f₄ (x)=x(x-1)(x-2)(x-3)/4!. Do the same for f₁ (x)=x/1!=x and f₀ (x)=1.

(iii) Conjecture the general pattern.

(iv) [Harder and optional] Prove your conjecture.

Exercise 12 (i) Let f(x)=Af₃ (x)+Bf₂ (x)+Cf₁ (x)+D. Find the table of successive differences as in the previous exercise. If we take it in the form

identify ?, ?, ? and ?.

(ii) If g is any cubic, show that we can find a, b, c and d such that

g(x)=af₃ (x)+bf₂ (x)+cf₁ (x)+d.

Hence show that g can be found from its table of successive differences.

(iii) Conjecture the general pattern.

(iv) [Harder and optional] Prove your conjecture.

We can extend the results of the last exercises a bit. Suppose that f is a polynomial of degree m. If we form the the following table of differences (here h> 0)

and so on, then

Exercise 13 [Optional] Prove this.

If we use formula *

for $0\leq k\leq mh$

then we say that we are interpolating . If we use formula * for k outside this region we say that we are extrapolating .

The sceptical reader may have noticed that, although we began our discussion by talking about tables of the sine function everything that followed dealt with polynomials. However, as the mathematicians of the 17th century discovered, the kind of `nice' functions that we wish to tabulate look very much like polynomials over small ranges of values. Since they look like polynomials, formula * which applies to polynomials will apply to them (to a very close approximation). We need only calculate our desired function at a small number of values and then we can use equation * to find its values at other points.

For example, here are the values of ln x at a certain number of values.

We obtain the following table of differences.

Thus, in equation * , ?₀ =1.60944, ?₁ =0.01980, ?₂ =-0.00038 and ?₄ =0.0001. We thus hope that

\[\ln(5+k)\approx1.60944+0.01980\frac{k}{h}+ -0.00019\frac{k(k-h)}{h^{2}}+ +0.00001\frac{k(k-h)(k-2h)}{6h^{3}}.\]

Trying this with $k=0.11$ gives \[\ln 5.11\approx 1.63120\]

and this turns out to be correct to the number of digits given.

Exercise 14 Compute ln 5.16 using our approximation. Compare this with the correct answer. Repeat the exercise for ln y where you choose y with

$5 < y < 5.4$.

Although functions like ln behave like polynomials over small ranges of values, they need not behave like polynomials over large ranges. It is thus not surprising that an idea which works well for interpolating (that is, trying to find the value of a function f at a point using values of f at points close by) works less well (or fails entirely) when we try to use it to guess the value of a function at points far away from those where we know its value.

Exercise 15 Compute ln 10 using our approximation. Compare this with the correct answer.

There is a much more serious problem associated with differencing which I have avoided mentioning up to now. So far, I have assumed that all the initial tabular values are given exactly. In reality, we usually work to a certain number of decimal places. Suppose that we round to the nearest integer. Then a table which looks like

with a table of differences

could actually represent

${ {1 \over 2} -{1 \over 2}{1 \over 2} -{1 \over 2}{1 \over 2} -{1 \over 2}{1 \over 2} -{1 \over 2} }$

with a table of differences

Thus if the first line of a table of differences is only known to an accuracy of epsilon; the second line is only known to an accuracy of 2 epsilon; and the nth line to an accuracy of 2ⁿ epsilon;.

In practice this means that, initially, the entries in successive lines of a table of differences will tend to decrease (just as we saw when we used exact arithmetic) but because the errors are increasing there will come a point when the errors swamp the calculation and the entries in successive lines will tend to increase.

As an example consider the entries in a table of sines (x represents degrees).

Here is the table of differences

It is clear that only the first two lines of the table of differences (and perhaps, if we think hard, the third) carry any information. In the remaining lines the `noise' of the errors drowns out everything else.

This means that when we interpolate we must confine ourselves to using the first two lines and our version of * will read

\[\sin (10+k)\approx0.1736+0.0172k.\]

(However, as the reader can verify, this remains a pretty accurate formula for $k$ with $0\leq k\leq 1$.)

Exercise16 Choose a table (or make your own) of some function, form the table of differences, note the line at which error noise becomes dominant. Use the part of the table above that line to interpolate at some point. Check the accuracy of your interpolation. It is very instructive to investigate how the number of significant figures and the spacing of the points of your table affect the result.

We can now see one way in which we can compile tables of a function f like ln or sin with a given level of accuracy. We compute f at a relatively small number of points to much higher accuracy than the table demands. (Of course, these calculations may be quite lengthy but we only need do a few of them.) We obtain the values at f at the remaining points by easy interpolation. Notice that once we have obtained a few points using * we can the build up the rest of the table using the techniques of Exercise 16.

For four hundred years science and technology depended on tables. Books of tables made it possible to find the orbits of the planets, to navigate the globe, and to make an industrial revolution. The book of logarithms was as much a symbol of science as the microscope. Yet, even then, few people bothered to celebrate the labours of the maker of tables. Nowadays their work is completely forgotten. I hope that this essay may help the reader appreciate the work of these unsung heros.

Dr Tom KÃrner is a Reader in the Department of Pure Mathematics and Mathematical Statistics at the University of Cambridge and a Fellow of Trinity Hall.