Find an Approximate Answer

(how close is good enough?)


Sometimes there is no exact solution to a problem.

Sometimes the problem has not yet been solved exactly.



The bin packing problem

The very first machine built by Charles Babbage in the early 1800s was the "Difference Engine", a device that computed the values of functions (such as a table of squares) based on the differences between successive values. The methodology is to take differences between successive pairs of values, and then the differences between the differences. This process is repeated until a column of differences is found in which the results are constant (or the next column is all zeros). In the case of squares, it is the second column of differences that is constant.

This is based on the following theorem:

The n-th differences of an n-th degree polynomial are all constant.
Obviously the n+1-th differences are all zero.

Once the column of constant values has been located (or a reasonable approximation thereto) we can extrapolate the table of values by extending the column of constants one more place and then derive the value in the next column (to the left) by adding the new difference to its corresponding value in the column to the left and above it.

Can you evaluate the next two squares by this method? (That is today's second post-class activity.) This method can also be used in approximating intermediate values in a set of regularly spaced observations and in extrapolating the next values.


Last updated 2000/05/05
© J.A.N. Lee, 2000.