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:
“Government by average opinion is merely a circuitous method of going to the devil; those who profess to lead but in fact slavishly follow this average opinion are simply the fastest runners and the loudest squeakers of the herd which is rushing blindly down to its destruction.”
—Thomas Henry Huxley (1825–95)
“... [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)
“Quintilian [educational writer in Rome about A.D. 100] hoped that teachers would be sensitive to individual differences of temperament and ability. . . . Beating, he thought, was usually unnecessary. A teacher who had made the effort to understand his pupil’s individual needs and character could probably dispense with it: “I will content myself with saying that children are helpless and easily victimized, and that therefore no one should be given unlimited power over them.””
—C. John Sommerville (20th century)