Prosthaphaeresis

From Wikipedia, the free encyclopedia

Prosthaphaeresis was an algorithm used in the late 16th century and early 17th century for approximating products using formulas from trigonometry. For the 25 years preceding the invention of the logarithm in 1614, it was the only known generally-applicable way of approximating products quickly. Its name comes from the Greek prosthesis and aphaeresis, meaning addition and subtraction, two steps in the process.

1 History and motivation
2 The identities
3 The algorithm
4 Decreasing the error
5 Reverse identities
6 Sources

[edit] History and motivation

A spherical triangle

In the sixteenth century, celestial navigation of European ships on long voyages at sea relied heavily on charts prepared by astronomers called ephemeral charts to determine their position and course. These voluminous documents detailed the position of various celestial objects in the sky at various points in time. The models used to compute these were based on spherical trigonometry, which relates the angles and arc lengths of spherical triangles such as the one in the diagram to the right using formulas such as the following:

cos a = cos b cos c + sin b sin c cos α
sin b sin α = sin a sin β

When one quantity in such a formula is unknown but the others are known, the unknown quantity can be computed using a series of multiplications, divisions, and trigonometric table lookups. Astronomers had to make thousands of such calculations, and because the only method of multiplication available was the grade-school method, most of this time was spent taxingly multiplying out products.

Mathematicians, particularly those who were also astronomers, were looking for an easier way, and trigonometry was one of the most advanced and familiar fields to these people. Prosthaphaeresis appeared in the 1580s, but its originator is not known for certain; its contributors included the mathematicians Paul Wittich, Ibn Yunis, Joost Bürgi, Johannes Werner, Christopher Clavius, and François Viète. Wittich, Yunis, and Clavius were all astronomers and have all been credited by various sources with discovering the method. Its most well-known proponent was Tycho Brahe, who used it extensively for astronomical calculations such as those described above. It was also used by John Napier, who is credited with inventing the logarithms that would supplant it.

Just as ordinary slide rules are based on logarithms, recently researchers have conceived a little-known slide rule based on prosthaphaeresis. [1]

[edit] The identities

The trigonometric identities exploited by prosthaphaeresis relate products of trigonometric functions to sums. They include the following:

sin a sin b = ½[cos(a - b) - cos(a + b)]
cos a cos b = ½[cos(a - b) + cos(a + b)]
sin a cos b = ½[sin(a + b) + sin(a - b)]
cos a sin b = ½[sin(a + b) - sin(a - b)]

The first two of these are believed to have been derived by Bürgi, who related them to Brahe; the others follow easily from these two. If both sides are multiplied by 2, these formulas are also called the Werner formulas.

[edit] The algorithm

Using the second formula above, the technique works as follows:

Scale down: By shifting the decimal point to the left or right, scale both numbers to a value between -1 and 1.
Inverse cosine: Using an inverse cosine table, find two angles whose cosines are our two values.
Sum and difference: Find the sum and difference of the two angles.
Average the cosines: Find the cosines of the sum and difference angles using a cosine table and average them.
Scale up: Shift the decimal place in the answer to the right (or left) as many places as you shifted the decimal place to the left (or right) in the first step, for each input.

For example, say we want to multiply 105 and 720. Following the steps:

Scale down: Shift the decimal 3 to the left in each. We get: 0.105, 0.720
Inverse cosine: cos(84°) is about 0.105, cos(44°) is about 0.720
Sum and difference: 84 + 44 = 128, 84 - 44 = 40
Average the cosines: ½[cos(128°) + cos(40°)] is about ½[-0.616 + 0.766], or 0.075
Scale up: We shifted 105 and 720 each 3 to the left, so shift our answer 6 to the right. The result is 75,000. This is very close to the actual product, 75,600.

If we want the product of the cosines of the two initial values, which is useful in some of the astronomical calculations mentioned above, this is surprisingly even easier: only steps 3 and 4 above are necessary.

Algorithms using the other formulas are similar, but each using different tables (sine, inverse sine, cosine, and inverse cosine) in different places. The first two are the easiest because they each only require two tables. Using the second formula, however, has the unique advantage that if only a cosine table is available, it can be used to estimate inverse cosines by searching for the angle with the nearest cosine value.

Notice how similar the above algorithm is to the process for multiplying using logarithms, which follows the steps: scale down, take logarithms, add, take inverse logarithm, scale up. It's no surprise that the originators of logarithms had used prosthaphaeresis.

[edit] Decreasing the error

If all the operations are performed with high precision, the product can be as accurate as desired. Although sums, differences, and averages are easy to compute with high precision, even by hand, trigonometric functions and especially inverse trigonometric functions are not. For this reason, the accuracy of the method depends to a large extent on the accuracy and detail of the trigonometric tables used.

For example, a sine table with an entry for each degree can be off by as much as 0.0087 if we just choose the closest number; each time we double the size of the table we halve this error. Tables were painstakingly constructed for prosthaphaeresis with values for every second, or 3600th of a degree.

Inverse sine and cosine functions are particularly troublesome, because they become steep near -1 and 1. One solution is to include more table values in this area. Another is to scale the inputs to numbers between -0.9 and 0.9. For example, 950 would become 0.095 instead of 0.950.

Another effective approach to enhancing the accuracy is linear interpolation, which chooses a value between two adjacent table values. For example, if we know the sine of 45° is about 0.707 and the sine of 46° is about 0.719, we can estimate the sine of 45.7° as:

0.707 × (1 - 0.7) + 0.719 × 0.7 = 0.7154.

The actual sine is 0.7157. A table of cosines with only 180 entries combined with linear interpolation is as accurate as a table with about 45000 entries without it. Even a quick estimate of the interpolated value is often much closer than the nearest table value. See lookup table for more details.

[edit] Reverse identities

The product formulas can also be manipulated to obtain formulas that express addition in terms of multiplication. Although less useful for computing products, these are still useful for deriving trigonometric results: