Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

The Difference Engine was doing only additions and subtractions. For additions and subtractions, it does not make sense to split the operands in smaller pieces and then chain the results by carry propagation. Or rather it does make sense, but this is exactly how they are implemented to begin with: the operands are split in groups of 1 digit each, and then the operation is done digit by digit, and there's carry from one digit to the next.

The Difference Engine does not do any multiplications.

As for the stupendous precision. I implemented a difference engine today in Excel to see what's going on. It's a very fun exercise, one can do it in 15 min. But be warned, you'll waste hours playing with the thing.

Here's how the Difference Engine works. You want to calculate a function f at the points 0,dx, 2dx, 3dx, etc. You do it inductively, using the formula

f(x + dx) = f(x) + f'(x)dx

But who is going to give you f'(x)? Well, you calculate that inductively too. Or more precisely (this is crucial) you calculate the whole f'(x)dx inductively:

f'(x + dx) dx = f'(x) dx + f''(x) dx^2

And then for f'' dx^2, you say

f''(x + dx) dx^2 = f''(x) dx^2 + f'''(x) dx^3

At some point you decide to stop, so you assume that a certain derivative is constant. That's the order of the scheme. Wikipedia states that the second Difference Engine envisioned by Babbage had an order of 7 and 31 digits of precision, but I suspect it's a mistake. I think it's more likely the order of 8. The 8'th derivative of log(x) evaluated at 1 is -7!=-5040. If you use a dx=0.0001 then you need to store the number 504010^-32 = 504 10^31.

So, I suspect Babbage was trying to produce log tables with increments of 0.0001 with a precision of six digits. If you look at the error of this scheme, you'll see that it grows exponentially, and after just 1000 steps the error is of the order of 10^-6. So you need to reset your starting point, and start again. You produce 1000 more logs, then you reset again. After a while, the scheme becomes better behaved (fundamentally because you move further away from the function's singularity, which is zero). By the time you are around 4, you can run 10000 steps while keeping the error below 10^-6.

Now, it looks like a successor of Babbage, Scheutz, actually built a difference engine. I think the guy deserves as much admiration, if not more, than Babbage himself. He used 15 digits and only 4th order differences. But if you look at engines with different orders, you'll find out that higher orders stop giving a significant bang for the buck after the 4th order.

Does 15 digits/4th order make sense? Well, only if you are quite smart, but I think Scheutz was plenty: the fourth order derivative of log at 1 is 3!=6, so you need to be able to store the number 60.0001^4=610^-16. But how do you do that if you only have 15 digits? Well very simple: you observe that for the first about 1000 steps, all the numbers in the table start with 0.0, so you don't store only the digits after that, and for that you only need 15 digits.



Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: