Monday, August 27, 2007

Difference Engineering

I've known about Babbage's Difference and Analytical Engines for a long time, but never known much about how they work. Finally I actually read a little information on the first one (in the context of Legos) and it's pretty interesting from both a mathematical and mechanical point of view. Based on the information on that page, I worked out a tiny additional step of my own (though surely Babbage himself already knew this).

First of all, the basic idea: The purpose of the Difference Engine was to pre-calculate tables of polynomials for books in the days before portable calculators. So you'd want to known 3x3 + 14x2 + 5 for all values of x from 1 to, say, 1000. As it happens, there's a clever little shortcut such that if you have a few values you can calculate the next one very simply using only addition from the previous answer (thus "Difference Engine").

So let's say f(x) = x2 + 3x.


x   f(x)   diff1  diff2 
1     4      -      -   
2    10      6      -   
3    18      8      2
4    28     10      2
5    40     12      2
See that second difference column is a constant. If we'd picked a polynomial of the 3rd degree, we'd have to work this out to the 3rd column. Fourth degree, 4th column, etc.

So to build a machine, all you need to do is set the value for x = 1 and set the Nth difference in the last column. It automatically adds that difference to the previous difference, which is cascaded upwards until f(x + 1) is arrived at. Then you go around again. All that is required is simple addition.

What isn't explained on that page (that I saw) was how to know ahead of time what that last difference is going to be. Sure, you can work out N rows to get that Nth column, but it would be nice if you could set the inputs from direct inspection of the polynomial. As a matter of fact, this is easy.

Say f(x) = ax2 + bx + c. Then the difference between two successive answers (i.e. the value in the first difference column) is going to be:

a(x+1)2 + b(x+1) + c - ax2 - bx - c
= ax2 + 2ax + a + bx + b + c - ax2 - bx - c
= 2ax + a + b

The difference between successive entries in THAT column are going to be:

2a(x+1) + a + b - 2ax - a - b
= 2ax + 2a + a + b - 2ax - a - b
= 2a

And if we look at our example, we did indeed get 2 * 1 as the constant in the last column.

Working this out for a 3rd degree polynomial gives 6a (where a is the coefficient of x3). Based on these two examples and looking at Pascal's Triangle, I predicted the value for a 4th degree would be 20. But it was actually 24.

In fact, if you work it out it should be clear that the constant difference will be a * n!, where a is the coefficient of the highest power of x and n is that power. It should be simple to prove this using induction, since all other terms always drop out and you muliply the coefficient by the power at each step on the way down.

So if I wanted to know what the constant difference was in the 5th column of differences for the polynomial 8x5 - 3x3 + 117, I just multiple 8 times 5! and get 960. I cram that, plus the initial value for x = 1 onto the machine and get cranking.

4 comments:

  1. sweet. you make it sound so easy . . . TOO easy. i guess you need values in each of the N columns before you can begin (not just the first and the last).

    ReplyDelete
  2. I was hoping no one would notice that I'd glossed over the issue of initial values in other columns. I didn't devote much thought to it since I was thinking of that last difference as the farthest outpost of the problem, so to speak.

    But actually, there's going to be an infinite number of equations with any given difference, so in some sense the initial values of the columns correspond to the coefficients somehow.

    Maybe there's a general solution for each column? For instance, the second difference of x^2 + 3x is going to be 2. But the first difference will be 2x. So in the first row (i.e. x = 1), that's just 2.

    Of course, the choice between evaluating the original polynomial at N different values of x vs deriving N sub-polynomials and evaluating each at x = 1 is a no-brainer.

    OTOH, these sub-polynomials are related to ordinary derivatives somehow. They are just rates of change and rates of change of rates of change, after all. So maybe discovering the sub-polynomials wouldn't be so hard.

    ReplyDelete
  3. Having said all that, I now remember that there's a thing called (IIRC) "method of finite differences" that basically is a kind of calculus for integers. That's probably what this is all actually based on and the Big Table O' Values explanation is just for the n00bs like me to comprehend.

    ReplyDelete
  4. Yeah, not too hard to discover the sub-polynomials. I mean you already found the 2nd column polynomial for 3rd degree polynomials.

    ReplyDelete