Method of Differences
The principle of a difference engine is Newton's method of divided differences. If the initial value of a polynomial (and of its finite differences) is calculated by some means for some value of X, the difference engine can calculate any number of nearby values, using the method generally known as the method of finite differences. For example, consider the quadratic polynomial
with the goal of tabulating the values p(0), p(1), p(2), p(3), p(4), and so forth. The table below is constructed as follows: the second column contains the values of the polynomial, the third column contains the differences of the two left neighbors in the second column, and the fourth column contains the differences of the two neighbors in the third column:
| x | p(x) = 2x2 − 3x + 2 | diff1(x) = ( p(x+1) - p(x) ) | diff2(x) = ( diff1(x+1) - diff1(x) ) |
|---|---|---|---|
| 0 | 2 | -1 | 4 |
| 1 | 1 | 3 | 4 |
| 2 | 4 | 7 | 4 |
| 3 | 11 | 11 | |
| 4 | 22 |
The numbers in the third values-column are constant. In fact, by starting with any polynomial of degree n, the column number n + 1 will always be constant. This is the crucial fact behind the success of the method.
This table was built from left to right, but it is possible to continue building it from right to left down a diagonal in order to compute more values. To calculate p(5) use the values from the lowest diagonal. Start with the fourth column constant value of 4 and copy it down the column. Then continue the third column by adding 4 to 11 to get 15. Next continue the second column by taking its previous value, 22 and adding the 15 from the third column. Thus p(5) is 22+15 = 37. In order to compute p(6), we iterate the same algorithm on the p(5) values: take 4 from the fourth column, add that to the third column's value 15 to get 19, then add that to the second column's value 37 to get 56, which is p(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 add. From one loop to the next, it needs to store 2 numbers—in this example (the last elements in the first and second columns). To tabulate polynomials of degree n, one needs sufficient storage to hold n numbers.
Babbage's difference engine No. 2, finally built in 1991, could hold 8 numbers of 31 decimal digits each and could thus tabulate 7th degree polynomials to that precision. The best machines from Scheutz could store 4 numbers with 15 digits each.
Read more about this topic: Difference Engine
Famous quotes containing the words method of, method and/or differences:
“Argument is conclusive ... but ... it does not remove doubt, so that the mind may rest in the sure knowledge of the truth, unless it finds it by the method of experiment.... For if any man who never saw fire proved by satisfactory arguments that fire burns ... his hearer’s mind would never be satisfied, nor would he avoid the fire until he put his hand in it ... that he might learn by experiment what argument taught.”
—Roger Bacon (c. 1214–1294)
“... [a] girl one day flared out and told the principal “the only mission opening before a girl in his school was to marry one of those candidates [for the ministry].” He said he didn’t know but it was. And when at last that same girl announced her desire and intention to go to college it was received with about the same incredulity and dismay as if a brass button on one of those candidate’s coats had propounded a new method for squaring the circle or trisecting the arc.”
—Anna Julia Cooper (1859–1964)
“Toddlerhood resembles adolescence because of the rapidity of physical growth and because of the impulse to break loose of parental boundaries. At both ages, the struggle for independence exists hand in hand with the often hidden wish to be contained and protected while striving to move forward in the world. How parents and toddlers negotiate their differences sets the stage for their ability to remain partners during childhood and through the rebellions of the teenage years.”
—Alicia F. Lieberman (20th century)