DIFFERENCE ENGINE

p(0)=2.0
	2.0-1.72=0.28
p(0.1)=1.72		0.28-0.24=0.04
	1.72-1.48=0.24
p(0.2)=1.48		0.24-0.20=0.04
	1.48-1.28=0.20
p(0.3)=1.28		0.20-0.16=0.04
	1.28-1.12=0.16
p(0.4)=1.12

Notice how the values in the third row are constant. This is no coincidence. In fact, if you start with any polynomial of degree n, the column number n + 1 will always be constant. This crucial fact makes the method work, as we will see next.

We constructed this table from the left to the right, but now we can continue it from the right to the left in order to compute more values of our polynomial.

To calculate p(0.5) we use the values from the lowest diagonal. We start with the rightmost column value of 0.04. Then we continue the second column by subtracting 0.04 from 0.16 to get 0.12. Next we continue the first column by taking its previous value, 1.12 and subtracting the 0.12 from the second column. Thus p(0.5) is 1.12-0.12 = 1.0. In order to compute p(0.6), we iterate the same algorithm on the p(0.5) values: take 0.04 from the third column, subtract that from the second column's value 0.12 to get 0.08, then subtract that from the first column's value 1.0 to get 0.92, which is p(0.6).

This process may be continued ad infinitum. The values of the polynomial are produced without ever having to multiply. A difference engine only needs to be able to subtract. From one loop to the next, it needs to store 2 numbers in our case (the last elements in the first and second columns); if we wanted to tabulate polynomials of degree n, we'd need enough storage to hold n numbers.

Babbage's difference engine No. 2, finally built in 1991, could hold 7 numbers of 31 decimal digits each and could thus tabulate 7th degree polynomials to that precision. The best machines from Scheutz were able to store 4 numbers with 15 digits each.

See also: The Difference Engine