How do calculators calculate sine?
Introduction
Sine, one of the fundamental trigonometric functions, plays a critical role in various fields, including mathematics, physics, engineering and computer science. The process of calculating it is non-trivial, especially when implemented in electronic calculators, where efficiency and accuracy are extremely important.
In previous posts in the series, we explored how calculators solve equations And How they calculate square roots. In this post, we'll explore the intricate process of calculating the sine function, starting with simple approximations and then moving on to more complex techniques.
How is sine calculated?
First, let's take a look at the sine function:
It is immediately noticeable that this function is periodic and that it has strong symmetry in the range from 0 to π/2:
In other words, it is enough to calculate the function in the interval [0;π/2]. After this, you can use reversal and sign change to obtain the finished value. One way to calculate sin(x) in a reduced interval is to use the well-known approximation using Taylor series:
Here's what the graph looks like:
Although this method is simple, we need to calculate very high powers, and in the vicinity of π/2 the approximation errors can become quite large. For example, when approximating to the ninth power, the result for π/2 would be 1.00000354258428. The error is 3e-6, which is pretty bad since most calculations are done to 15 decimal places. In other words, we lose about 10 digits of accuracy!
How is sine actually calculated?
Although the method presented above is quite inaccurate, it serves as a basis for better methods. Essentially, all implementations of sine use the following three steps:
Casting: Using algebraic tricks we reduce x to a smaller number r.
Approximation: We calculate the value of sin(r) using approximation methods, for example, Taylor series.
Recreation: we calculate the final value of sin(x) based on sin(r).
There are many ways to solve this problem. Below I have presented the one that, judging by article Intel company uses it in its processors. They start with the formula
Here N is an integer chosen to minimize |r|. In other words, we approximate x using N⋅π/16, and r is the approximation error. How can this be used? Thanks to the identical equalities of the sums of arguments:
We need to calculate sin(r) and cos(r) – this is the approximation stage, which will be discussed in more detail below. For now, let's assume that we know both sin(r) and cos(r). We still need to find the sine and cosine of (N/32)2π. Let us note that both sine and cosine have a period of 2π, so we only need to calculate N for N=0,1,2,…,31. There are only 32 values, we can easily calculate them in advance. When calculating the final value, we just need to take them from the list, which is quite efficient.
There is only one piece of the puzzle left: how to calculate sin(r)? In the paper, Intel did not publish a specific polynomial, but did mention that it used a minimax approximation. This approximation finds the polynomial and minimizes the maximum error on the interval:
where p is the approximating polynomial. One way to calculate it is Remez algorithm. The results might look like this:
The maximum error of this polynomial is 4.1⋅10−9which is a thousand times better than the original Taylor series approximation!
Conclusion
To calculate the sine on a computer, you need to use the stages of reduction, approximation, and reconstruction. Computers use various techniques to calculate sine efficiently while maintaining an acceptable level of accuracy. Understanding these techniques sheds light on the calculations underlying computational tools and simulations in various fields.
[Прим. пер.: тригонометрические функции на разных архитектурах процессора, операционных системах и языках программирования могут давать разный ответ.]
