Prosthaphaeresis
Encyclopedia
Prosthaphaeresis was an algorithm
used in the late 16th century and early 17th century for approximate multiplication
and division
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.
In sixteenth century Europe, celestial navigation
of ships on long voyages relied heavily on ephemerides to determine their position and course. These voluminous charts prepared by astronomer
s detailed the position of stars and planets 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 (see diagram, right) using formulas such as:
where a, b and c are the angles subtended at the centre of the sphere by the corresponding arcs.
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 best method of multiplication available was long multiplication, 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.
(Additional information: Nicholas Copernicus mentions 'prosthaphaeresis' several times in his work De Revolutionibus Orbium Coelestium, published in 1543, meaning the "great parallax" caused by the displacement of the observer due to the Earth's annual motion.)
s to sums. They include the following:
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.
For example, say we want to multiply 105 and 720. Following the steps:
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.
A table of secant
s can be used for division. To divide 3746 by 82.05, we scale the numbers to 0.3746 and 8.205. The first is approximated as the cosine of 68 degrees, and the second as the secant of 83 degrees. Exploiting the definition of the secant as the reciprocal of the cosine, we proceed as in multiplication above: Average the cosine of the sum of the angles, 151, with the cosine of their difference, 15.
Scaling up to locate the decimal point gives the approximate answer, 46.
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.
Indeed the two are closely related mathematically. In modern terms, prosthaphaeresis can be viewed as relying on the logarithm of complex numbers, in particular on the identity e^(ix)=cos x + i sin x.
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:
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.
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
used in the late 16th century and early 17th century for approximate multiplication
Multiplication
Multiplication is the mathematical operation of scaling one number by another. It is one of the four basic operations in elementary arithmetic ....
and division
Division (mathematics)
right|thumb|200px|20 \div 4=5In mathematics, especially in elementary arithmetic, division is an arithmetic operation.Specifically, if c times b equals a, written:c \times b = a\,...
using formulas from trigonometry
Trigonometry
Trigonometry is a branch of mathematics that studies triangles and the relationships between their sides and the angles between these sides. Trigonometry defines the trigonometric functions, which describe those relationships and have applicability to cyclical phenomena, such as waves...
. For the 25 years preceding the invention of the logarithm
Logarithm
The logarithm of a number is the exponent by which another fixed value, the base, has to be raised to produce that number. For example, the logarithm of 1000 to base 10 is 3, because 1000 is 10 to the power 3: More generally, if x = by, then y is the logarithm of x to base b, and is written...
in 1614, it was the only known generally-applicable way of approximating products quickly. Its name comes from the Greek
Greek language
Greek is an independent branch of the Indo-European family of languages. Native to the southern Balkans, it has the longest documented history of any Indo-European language, spanning 34 centuries of written records. Its writing system has been the Greek alphabet for the majority of its history;...
prosthesis and aphaeresis, meaning addition and subtraction, two steps in the process.
History and motivation
Celestial navigation
Celestial navigation, also known as astronavigation, is a position fixing technique that has evolved over several thousand years to help sailors cross oceans without having to rely on estimated calculations, or dead reckoning, to know their position...
of ships on long voyages relied heavily on ephemerides to determine their position and course. These voluminous charts prepared by astronomer
Astronomer
An astronomer is a scientist who studies celestial bodies such as planets, stars and galaxies.Historically, astronomy was more concerned with the classification and description of phenomena in the sky, while astrophysics attempted to explain these phenomena and the differences between them using...
s detailed the position of stars and planets at various points in time. The models used to compute these were based on spherical trigonometry
Spherical trigonometry
Spherical trigonometry is a branch of spherical geometry which deals with polygons on the sphere and the relationships between the sides and the angles...
, which relates the angles and arc lengths of spherical triangles (see diagram, right) using formulas such as:
- cos a = cos b cos c + sin b sin c cos α
- sin b sin α = sin a sin β
where a, b and c are the angles subtended at the centre of the sphere by the corresponding arcs.
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 best method of multiplication available was long multiplication, 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
Paul Wittich
Paul Wittich was a German mathematician and astronomer whose Capellan geoheliocentric model, in which the inner planets Mercury and Venus orbit the sun but the outer planets Mars, Jupiter and Saturn orbit the Earth, may have directly inspired Tycho Brahe's more radically heliocentric...
, Ibn Yunis, Joost Bürgi
Joost Bürgi
Jost Bürgi, or Joost, or Jobst Bürgi , active primarily at the courts in Kassel and Prague, was a Swiss clockmaker, a maker of astronomical instruments and a mathematician....
, Johannes Werner
Johannes Werner
Johann Werner was a German parish priest in Nuremberg and a mathematician...
, Christopher Clavius
Christopher Clavius
Christopher Clavius was a German Jesuit mathematician and astronomer who was the main architect of the modern Gregorian calendar...
, and François Viète
François Viète
François Viète , Seigneur de la Bigotière, was a French mathematician whose work on new algebra was an important step towards modern algebra, due to its innovative use of letters as parameters in equations...
. 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
Tycho Brahe
Tycho Brahe , born Tyge Ottesen Brahe, was a Danish nobleman known for his accurate and comprehensive astronomical and planetary observations...
, who used it extensively for astronomical calculations such as those described above. It was also used by John Napier
John Napier
John Napier of Merchiston – also signed as Neper, Nepair – named Marvellous Merchiston, was a Scottish mathematician, physicist, astronomer & astrologer, and also the 8th Laird of Merchistoun. He was the son of Sir Archibald Napier of Merchiston. John Napier is most renowned as the discoverer...
, who is credited with inventing the logarithms that would supplant it.
(Additional information: Nicholas Copernicus mentions 'prosthaphaeresis' several times in his work De Revolutionibus Orbium Coelestium, published in 1543, meaning the "great parallax" caused by the displacement of the observer due to the Earth's annual motion.)
The identities
The trigonometric identities exploited by prosthaphaeresis relate products of trigonometric functionTrigonometric function
In mathematics, the trigonometric functions are functions of an angle. They are used to relate the angles of a triangle to the lengths of the sides of a triangle...
s 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.
The algorithm
Using the second formula above, the technique for multiplication 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 point three places 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: For each of 105 and 720 we shifted the decimal point three places to the left, so in the answer we shift six places 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.
A table of secant
Trigonometric function
In mathematics, the trigonometric functions are functions of an angle. They are used to relate the angles of a triangle to the lengths of the sides of a triangle...
s can be used for division. To divide 3746 by 82.05, we scale the numbers to 0.3746 and 8.205. The first is approximated as the cosine of 68 degrees, and the second as the secant of 83 degrees. Exploiting the definition of the secant as the reciprocal of the cosine, we proceed as in multiplication above: Average the cosine of the sum of the angles, 151, with the cosine of their difference, 15.
- ½[cos(151°) + cos(−15°)] is about ½[−0.875 + 0.966], or 0.046
Scaling up to locate the decimal point gives the approximate answer, 46.
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.
Indeed the two are closely related mathematically. In modern terms, prosthaphaeresis can be viewed as relying on the logarithm of complex numbers, in particular on the identity e^(ix)=cos x + i sin x.
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
Linear interpolation
Linear interpolation is a method of curve fitting using linear polynomials. Lerp is an abbreviation for linear interpolation, which can also be used as a verb .-Linear interpolation between two known points:...
, 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
Lookup table
In computer science, a lookup table is a data structure, usually an array or associative array, often used to replace a runtime computation with a simpler array indexing operation. The savings in terms of processing time can be significant, since retrieving a value from memory is often faster than...
for more details.
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:- sin a + sin b = 2sin[½(a + b)]cos[½(a − b)]
- sin a − sin b = 2cos[½(a + b)]sin[½(a − b)]
- cos a + cos b = 2cos[½(a + b)]cos[½(a − b)]
- cos a − cos b = −2sin[½(a + b)]sin[½(a − b)]
External links
- PlanetMath: Prosthaphaeresis formulas
- Daniel E. Otero Henry Briggs. Introduction: the need for speed in calculation.
- Mathworld: Prosthaphaeresis formulas
- Adam Mosley. Tycho Brahe and Mathematical Techniques. University of Cambridge.
- IEEE Computer Society. History of computing: John Napier and the invention of logarithms.
- Math Words: Prosthaphaeresis
- Beatrice Lumpkin. African and African-American Contributions to Mathematics. Discusses Ibn Yunis's contribution to prosthaphaeresis.
- Prosthaphaeresis and beat phenomenon in the theory of vibrations, by Nicholas J. Rose