I don't know how many readers here remember doing math BC (that is, Before Calculators), but imagine if you will.....
You are a surveyor or cartographer, who's job is to make a map of a previously unmapped area. So you find easily visible landmarks -- very visible trees, church pinnacles, mountain tops, etc -- and try to accurately measure their position so you can map them. You do this by very accurately measuring the distance between two known points, then very accurately measuring the angles from one known point and an unknown point; then from the other known point and the same unknown point. At that point, you consider the unknown point as "known". So you then measure more angles, trek to new "known" points, measure more angles, etc, etc, etc, until you have lots and lots of measured points.
Then you take your logs, retire to your office, tent, or room at the inn, and start calculating. There's a simple to understand formula for calculating the unknown legs of the triangles if you know the angles. For any given triangle, the ratio of the length of a side to the sine of the opposite angle is constant -- and you have the length of one side and all three angles. All you have to do in your calculating (and remember, you are working with pencil and paper, no calculator) is to find the sine of every angle you have measured, and start plugging them into this formula to come up with the length of the unknown sides.
For a moderately complex map, there may be a hundred triangles or so, so you have a few hundred sines to compute. And the accuracy of your map is determined by a combination of how accurately and precisely you measure your angles, and how accurate and precise your computed sine values.
Of course, values of sines, cosines, tangents, logarithms, etc are also commonly needed for navigation, engineering, gunnery, chemical, architectural, and many other purposes than just surveying/cartographic purposes.
As an estimate, I decided to compute (by hand) the sine of two arbitrary angles (37.5 and 17.5 degrees) to see exactly how long it would take to compute them to 4 digits of accuracy....... OK, I only did one (37.5), and it took me about 45 minutes. With practice I could probably get better at it. I was also unsure of the level of precision I needed in my intermediate results, so I overdid it and got nearly 6 digits of accuracy (0.6087707 hand-calculated versus 0.608761429 by computer). But even at a half-hour per computation, it is clearly very laborious.
Obviously, doing these sorts of calculations by hand is a ludicrous task for the working surveyor, engineer, architect, etc. And imagine trying to do it in the heat of battle -- a gunner wants the angle he needs to aim the gun now, not in 45 minutes.
The solution is tables -- spend the laborious job calculating the necessary transcendental functions for a large range of values. That way, when an engineer needs to know the value of the sine of 37.5 degrees, he simply consults the table and reads off 0.6088 and gets the value he needs in 15 seconds rather than in half an hour.
Of course, you have to do the calculations and doublecheck the tables, and then make sure they get type-set correctly, etc. And there are a lot of values to check. I have in my possession a table, originally published in 1901, that contains the values of the six principle circular trigonometric functions for 385 different angles between 0 and 45 degrees, for over 2300 distinct values that were calculated. And I've no reason to doubt that this table was originally calculated by hand.
When calculating a large table like that, there are tricks to speed up the calculation. The major one being the "method of differences", which reduces the calculations required for each item on the table from 4 multiplications, 2 divisions, and 3 additions to only 6 additions. This is what I'll elaboate on next.
The method of differences is based on the idea that successive values in the tables differ in a predictable way, so you can simply add an easily computed value to one entry in the table to get the next, etc. Essentially, you compute the difference from one table entry to the next instead of computing the entire new value. This works if the difference is easier to compute than each new value; an assumption we have no reason, a priori, to believe.
Fortunately, a large, important class of function, polynomials, work very well by this method because the differences between successive values of a nth polynomial is an (n-1)th degree polynomial, which is definitely easier to compute than the original polynomial. In fact, it can be computed quickly and easily using the method of differences.
An example is in order. Let's say we wanted to compute the value of the 2nd degree polynomial f(x)=1-x2/2 for values of x=0, 0.01, 0.02, etc.
We can compute the 1st difference function of the polynomial by evaluating Df(x) = f(x+0.01)-f(x) to get Df(x) = -0.01x - 0.00005. Computing the difference function for this (the 2nd difference function of f(x), you get DDf(x) = 0.0001. This second difference function is real easy to compute.
So if we now build a table with columns of x, f(x), Df(x), and DDf(x), we can easily compute successive lines by remembering that f(x+0.1) = f(x) + Df(x), Df(x+0.01) = Df(x) + DDf(x), and DDf(x) = -0.0001. The table looks like this:
The last column (the cosine of x, where x is in radians) will give you a clue as to why I chose that particular quadratic polynomial. 1-x2/2 is a very good quadratic approximation of cos(x), and is off by less than 2% at x=pi/4 (45 degrees). On this table (which only covers about 6 degrees) it is accurate to one part in 10,000.
This example highlights two points: First, if f(x) is an nth degree polynomial, then Dnf(x) is constant, which makes computing successive values of f(x) as easy as doing n additions. Second, transcendental functions can be effectively approximated by polynomials. sin(x), for instance, can be approximated by a 7-th degree polynomial which is accurate (over 45 degrees) to 1 part per 3 million. And this polynomial can be tabulated with only 7 additions per entry. This is a vast improvement over 30 minutes per entry.
But it is still error-prone if done by hand, and errors tend to add up, horribly. If I miscalculated one entry in the Df(x) column, then the f(x) column will diverge from the correct value linearly with more and more entries. A mistake in the DDDf(x) column will make the final value diverge with the 3rd power. Even without mathematical errors, errors were still possible when typesetting the resulting tables. And errors in tables could (and did) lead to costly or fatal mistakes. So great the problems of errors and time of calculation that in the early 1800's one of Charles Babbage's superiors stated that he would love to see a way of making tables "by steam".
This sets the stage for Charles Babbage in the early 19th century, when he designed his "difference engine". He took this challenge, and designed not one, but three different machines to calculate tables "by steam". None of them were ever built by Babbage, because of issues of money, politics, and pissing off his mechanic. That, and no one around him learned the first rule of commercializing and engineering project: You have to know when take the plans out of the hands of the engineer and build it.
Next week, I'll describe the last one he designed, and the one which was finally built in 1991: the Difference Engine #2.
The Problem
You are a surveyor or cartographer, who's job is to make a map of a previously unmapped area. So you find easily visible landmarks -- very visible trees, church pinnacles, mountain tops, etc -- and try to accurately measure their position so you can map them. You do this by very accurately measuring the distance between two known points, then very accurately measuring the angles from one known point and an unknown point; then from the other known point and the same unknown point. At that point, you consider the unknown point as "known". So you then measure more angles, trek to new "known" points, measure more angles, etc, etc, etc, until you have lots and lots of measured points.
Then you take your logs, retire to your office, tent, or room at the inn, and start calculating. There's a simple to understand formula for calculating the unknown legs of the triangles if you know the angles. For any given triangle, the ratio of the length of a side to the sine of the opposite angle is constant -- and you have the length of one side and all three angles. All you have to do in your calculating (and remember, you are working with pencil and paper, no calculator) is to find the sine of every angle you have measured, and start plugging them into this formula to come up with the length of the unknown sides.
For a moderately complex map, there may be a hundred triangles or so, so you have a few hundred sines to compute. And the accuracy of your map is determined by a combination of how accurately and precisely you measure your angles, and how accurate and precise your computed sine values.
Of course, values of sines, cosines, tangents, logarithms, etc are also commonly needed for navigation, engineering, gunnery, chemical, architectural, and many other purposes than just surveying/cartographic purposes.
As an estimate, I decided to compute (by hand) the sine of two arbitrary angles (37.5 and 17.5 degrees) to see exactly how long it would take to compute them to 4 digits of accuracy....... OK, I only did one (37.5), and it took me about 45 minutes. With practice I could probably get better at it. I was also unsure of the level of precision I needed in my intermediate results, so I overdid it and got nearly 6 digits of accuracy (0.6087707 hand-calculated versus 0.608761429 by computer). But even at a half-hour per computation, it is clearly very laborious.
Obviously, doing these sorts of calculations by hand is a ludicrous task for the working surveyor, engineer, architect, etc. And imagine trying to do it in the heat of battle -- a gunner wants the angle he needs to aim the gun now, not in 45 minutes.
The solution is tables -- spend the laborious job calculating the necessary transcendental functions for a large range of values. That way, when an engineer needs to know the value of the sine of 37.5 degrees, he simply consults the table and reads off 0.6088 and gets the value he needs in 15 seconds rather than in half an hour.
Of course, you have to do the calculations and doublecheck the tables, and then make sure they get type-set correctly, etc. And there are a lot of values to check. I have in my possession a table, originally published in 1901, that contains the values of the six principle circular trigonometric functions for 385 different angles between 0 and 45 degrees, for over 2300 distinct values that were calculated. And I've no reason to doubt that this table was originally calculated by hand.
When calculating a large table like that, there are tricks to speed up the calculation. The major one being the "method of differences", which reduces the calculations required for each item on the table from 4 multiplications, 2 divisions, and 3 additions to only 6 additions. This is what I'll elaboate on next.
The Method of Differences
The method of differences is based on the idea that successive values in the tables differ in a predictable way, so you can simply add an easily computed value to one entry in the table to get the next, etc. Essentially, you compute the difference from one table entry to the next instead of computing the entire new value. This works if the difference is easier to compute than each new value; an assumption we have no reason, a priori, to believe.
Fortunately, a large, important class of function, polynomials, work very well by this method because the differences between successive values of a nth polynomial is an (n-1)th degree polynomial, which is definitely easier to compute than the original polynomial. In fact, it can be computed quickly and easily using the method of differences.
An example is in order. Let's say we wanted to compute the value of the 2nd degree polynomial f(x)=1-x2/2 for values of x=0, 0.01, 0.02, etc.
We can compute the 1st difference function of the polynomial by evaluating Df(x) = f(x+0.01)-f(x) to get Df(x) = -0.01x - 0.00005. Computing the difference function for this (the 2nd difference function of f(x), you get DDf(x) = 0.0001. This second difference function is real easy to compute.
So if we now build a table with columns of x, f(x), Df(x), and DDf(x), we can easily compute successive lines by remembering that f(x+0.1) = f(x) + Df(x), Df(x+0.01) = Df(x) + DDf(x), and DDf(x) = -0.0001. The table looks like this:
x f(x) Df(x) DDf(x) cos(x) ===== ======== ======== ======== ======== +0.00 +1.00000 -0.00005 -0.00010 +1.00000 +0.01 +0.99995 -0.00015 -0.00010 +0.99995 +0.02 +0.99980 -0.00025 -0.00010 +0.99980 +0.03 +0.99955 -0.00035 -0.00010 +0.99955 +0.04 +0.99920 -0.00045 -0.00010 +0.99920 +0.05 +0.99875 -0.00055 -0.00010 +0.99875 +0.06 +0.99820 -0.00065 -0.00010 +0.99820 +0.07 +0.99755 -0.00075 -0.00010 +0.99755 +0.08 +0.99680 -0.00085 -0.00010 +0.99680 +0.09 +0.99595 -0.00095 -0.00010 +0.99595 +0.10 +0.99500 -0.00105 -0.00010 +0.99500 +0.11 +0.99395 -0.00115 -0.00010 +0.99396
The last column (the cosine of x, where x is in radians) will give you a clue as to why I chose that particular quadratic polynomial. 1-x2/2 is a very good quadratic approximation of cos(x), and is off by less than 2% at x=pi/4 (45 degrees). On this table (which only covers about 6 degrees) it is accurate to one part in 10,000.
This example highlights two points: First, if f(x) is an nth degree polynomial, then Dnf(x) is constant, which makes computing successive values of f(x) as easy as doing n additions. Second, transcendental functions can be effectively approximated by polynomials. sin(x), for instance, can be approximated by a 7-th degree polynomial which is accurate (over 45 degrees) to 1 part per 3 million. And this polynomial can be tabulated with only 7 additions per entry. This is a vast improvement over 30 minutes per entry.
But it is still error-prone if done by hand, and errors tend to add up, horribly. If I miscalculated one entry in the Df(x) column, then the f(x) column will diverge from the correct value linearly with more and more entries. A mistake in the DDDf(x) column will make the final value diverge with the 3rd power. Even without mathematical errors, errors were still possible when typesetting the resulting tables. And errors in tables could (and did) lead to costly or fatal mistakes. So great the problems of errors and time of calculation that in the early 1800's one of Charles Babbage's superiors stated that he would love to see a way of making tables "by steam".
This sets the stage for Charles Babbage in the early 19th century, when he designed his "difference engine". He took this challenge, and designed not one, but three different machines to calculate tables "by steam". None of them were ever built by Babbage, because of issues of money, politics, and pissing off his mechanic. That, and no one around him learned the first rule of commercializing and engineering project: You have to know when take the plans out of the hands of the engineer and build it.
Next week, I'll describe the last one he designed, and the one which was finally built in 1991: the Difference Engine #2.
2 comments | Leave a comment
![[info]](http://l-stat.livejournal.com/img/userinfo.gif?v=91.7){kind=small}
