Babbage’s Difference Engine

Babbage's Difference Engine is pretty fascinating. I had wanted to go see the one on display at the Computer History Museum in Mountain View, but now Nathan Myhrvold has the thing back in his living room! Maybe I’ll build one out of Legos to keep in my office.

The physical engineering is amazing with 8,000 moving parts! But, it’s very cool how it works mathematically. Let’s try it out in Excel. We can use any polynomial function (say, 2x^2-3x+2):

Now if we take the differences between pairs of results and then differences between those differences, we end up with a constant in the d2 column. For higher order polynomials we may have to continue out more columns before arriving at a constant (Babbage’s actual machine handles up to 7^th order).

The super-interesting thing to notice is that, now that we know the first row, we can turn this on its side and derive each subsequent row by just adding the differences back together.

We can do a Fill Down in Excel and reproduce the whole series using only addition!

I thought it'd be cool to make an infinite Seq generator using the method of differences:

let engine =

    let uncurry f (a, b) = f a b

    let flip f a b = f b a

    let next =

        Seq.pairwise

        >> Seq.map (uncurry (+))

        >> (flip Seq.append) [0]

    Seq.unfold (fun d -> Some(Seq.hd d, next d))

Then we can "seed the columns" and crank away... For example:

engine [7; 0]

... produces an infinite sequence of 7s. Simple enough. Or:

engine [1; 1; 0]

... produces all the natural numbers (1, 2, 3, 4, 5, ... to infinity). It works with any polynomial function! For example f(x) = x^2 (squared), can be given by:

engine [1; 3; 2; 0]

... or of course the one we did in Excel, f(x) = 2x^2 - 3x + 2 is just:

engine [1; 3; 4; 0]

Kind of amazing! :-)