3 ms·

People already had tables of logarithms with lower precision. At the time he did a survey of what tables were available in the world, and it turned out the Fren

People already had tables of logarithms with lower precision. At the time he did a survey of what tables were available in the world, and it turned out the French had just produced some quite impressive tables, using a lot of manual labor. His value proposition to the British Government was that he can deliver something even better at a fraction of the manual labor (basically only a few people to turn on the crank). The Brits were enamored with the concept of automation at the time, and he made a proof of concept machine with lower precision that he was very happy to demonstrate wherever he would go. Why did he aim for 40 digits? Maybe he did some back of the envelope estimation for the error propagation. If you start with an average error of 10^(-40), then after n additions, in the worst case you can have an error of n*10^(-40). Which is not so bad. But the problem is that in the difference engine you end up adding intermediate results to intermediate results, many, many times over. So if you only look at the worst possible results, you end up needing a lot of precision to start with. Of course, nowadays we know better how to analyze the propagation of errors, but in his time he either didn't know how, or he couldn't convince other people that he can get the total error under control if he used a lower precision throughout. In any case, he completely underestimated the difficulty of scaling the project from his toy example to the full blown final machine.

monocasa 5y ago
They had tables, but they were rife with errors. Some accidental, some intentional as a form of copy protection. Britain didn't respect French copyright at the time, so as soon as they put their hands on a book it would have been fine to copy. Therefore his proposition was for accuracy from mechanical nature of what he was proposing. And everything you said doesn't discount using a lower precision ALU, and chaining the results with carry propagation. We do that today; every Diffie-Hellman your computer performs involves numbers far larger than it's ALU width. And bit serial machines have a long history.
- credit_guy 5y ago
  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.

monocasa 5y ago

They had tables, but they were rife with errors. Some accidental, some intentional as a form of copy protection. Britain didn't respect French copyright at the time, so as soon as they put their hands on a book it would have been fine to copy. Therefore his proposition was for accuracy from mechanical nature of what he was proposing. And everything you said doesn't discount using a lower precision ALU, and chaining the results with carry propagation. We do that today; every Diffie-Hellman your computer performs involves numbers far larger than it's ALU width. And bit serial machines have a long history.

credit_guy 5y ago
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.