How do Trigonometric functions work? [closed]

So in high school math, and probably college, we are taught how to use trig functions, what they do, and what kinds of problems they solve. But they have always been presented to me as a black box. If you need the Sine or Cosine of something, you hit the sin or cos button on your calculator and you're set. Which is fine.

What I'm wondering is how trigonometric functions are typically implemented.

Solution 1:

First, you have to do some sort of range reduction. Trig functions are periodic, so you need to reduce arguments down to a standard interval. For starters, you could reduce angles to be between 0 and 360 degrees. But by using a few identities, you realize you could get by with less. If you calculate sines and cosines for angles between 0 and 45 degrees, you can bootstrap your way to calculating all trig functions for all angles.

Once you've reduced your argument, most chips use a CORDIC algorithm to compute the sines and cosines. You may hear people say that computers use Taylor series. That sounds reasonable, but it's not true. The CORDIC algorithms are much better suited to efficient hardware implementation. (Software libraries may use Taylor series, say on hardware that doesn't support trig functions.) There may be some additional processing, using the CORDIC algorithm to get fairly good answers but then doing something else to improve accuracy.

There are some refinements to the above. For example, for very small angles theta (in radians), sin(theta) = theta to all the precision you have, so it's more efficient to simply return theta than to use some other algorithm. So in practice there is a lot of special case logic to squeeze out all the performance and accuracy possible. Chips with smaller markets may not go to as much optimization effort.

Solution 2:

edit: Jack Ganssle has a decent discussion in his book on embedded systems, "The Firmware Handbook".

FYI: If you have accuracy and performance constraints, Taylor series should not be used to approximate functions for numerical purposes. (Save them for your Calculus courses.) They make use of the analyticity of a function at a single point, e.g. the fact that all its derivatives exist at that point. They don't necessarily converge in the interval of interest. Often they do a lousy job of distributing the function approximation's accuracy in order to be "perfect" right near the evaluation point; the error generally zooms upwards as you get away from it. And if you have a function with any noncontinuous derivative (e.g. square waves, triangle waves, and their integrals), a Taylor series will give you the wrong answer.

The best "easy" solution, when using a polynomial of maximum degree N to approximate a given function f(x) over an interval x0 < x < x1, is from Chebyshev approximation; see Numerical Recipes for a good discussion. Note that the Tj(x) and Tk(x) in the Wolfram article I linked to used the cos and inverse cosine, these are polynomials and in practice you use a recurrence formula to get the coefficients. Again, see Numerical Recipes.

edit: Wikipedia has a semi-decent article on approximation theory. One of the sources they cite (Hart, "Computer Approximations") is out of print (& used copies tend to be expensive) but goes into a lot of detail about stuff like this. (Jack Ganssle mentions this in issue 39 of his newsletter The Embedded Muse.)

edit 2: Here's some tangible error metrics (see below) for Taylor vs. Chebyshev for sin(x). Some important points to note:

1. that the maximum error of a Taylor series approximation over a given range, is much larger than the maximum error of a Chebyshev approximation of the same degree. (For about the same error, you can get away with one fewer term with Chebyshev, which means faster performance)
2. Range reduction is a huge win. This is because the contribution of higher order polynomials shrinks down when the interval of the approximation is smaller.
3. If you can't get away with range reduction, your coefficients need to be stored with more precision.

Don't get me wrong: Taylor series will work properly for sine/cosine (with reasonable precision for the range -pi/2 to +pi/2; technically, with enough terms, you can reach any desired precision for all real inputs, but try to calculate cos(100) using Taylor series and you can't do it unless you use arbitrary-precision arithmetic). If I were stuck on a desert island with a nonscientific calculator, and I needed to calculate sine and cosine, I would probably use Taylor series since the coefficients are easy to remember. But the real world applications for having to write your own sin() or cos() functions are rare enough that you'd be best off using an efficient implementation to reach a desired accuracy -- which the Taylor series is not.

Range = -pi/2 to +pi/2, degree 5 (3 terms)

• Taylor: max error around 4.5e-3, f(x) = x-x³/6+x⁵/120
• Chebyshev: max error around 7e-5, f(x) = 0.9996949x-0.1656700x³+0.0075134x⁵

Range = -pi/2 to +pi/2, degree 7 (4 terms)

• Taylor: max error around 1.5e-4, f(x) = x-x³/6+x⁵/120-x⁷/5040
• Chebyshev: max error around 6e-7, f(x) = 0.99999660x-0.16664824x³+0.00830629x⁵-0.00018363x⁷

Range = -pi/4 to +pi/4, degree 3 (2 terms)

• Taylor: max error around 2.5e-3, f(x) = x-x³/6
• Chebyshev: max error around 1.5e-4, f(x) = 0.999x-0.1603x³

Range = -pi/4 to +pi/4, degree 5 (3 terms)

• Taylor: max error around 3.5e-5, f(x) = x-x³/6+x⁵
• Chebyshev: max error around 6e-7, f(x) = 0.999995x-0.1666016x³+0.0081215x⁵

Range = -pi/4 to +pi/4, degree 7 (4 terms)

• Taylor: max error around 3e-7, f(x) = x-x³/6+x⁵/120-x⁷/5040
• Chebyshev: max error around 1.2e-9, f(x) = 0.999999986x-0.166666367x³+0.008331584x⁵-0.000194621x⁷

Solution 3:

I believe they're calculated using Taylor Series or CORDIC. Some applications which make heavy use of trig functions (games, graphics) construct trig tables when they start up so they can just look up values rather than recalculating them over and over.