How are logarithms programmed?

Whether they are simply calculated using the same mechanism as linear search, or the range is somehow narrowed down like a binary search.

+7
source share
2 answers

The implementation of a function such as the natural logarithm in any decent mathematical library will contain an error below ulp (unit of least accuracy). The goal of the developer of the mathematical library is to find the optimal approximation, which allows to achieve the desired accuracy with minimal calculations. The Taylor series is usually a bad choice because too many terms are required to achieve the desired accuracy.

A typical weapon of choice is to reduce the range from all represented real numbers to some very small area, and then use some optimal approximation, which gives an exact approximation of the desired function in this narrow range. A typical weapon of choice for this optimal approximation is a polynomial or rational polynomial (the ratio of two polynomials). The implementation contains only polynomial coefficients. These coefficients are built using some optimization technique, such as the Remes Exchange algorithm.

In the case of the natural logarithm, there is a simple way to reduce the range. Real numbers are almost universally represented in terms of mantissa and exponent: x = m * 2 p where p is an integer and m is between 1 and 2. Thus, log ( x ) = log ( m ) + p> * log (2 ) The last member of p * log (2) is simply multiplication by a known constant. Thus, the problem boils down to finding the logarithm of a number from 1 to 2 (or between 1/2 and 1). A further reduction in the range can be done using the fact that √2 is logarithmically in the middle [1,2]. So all you need is a way to calculate the logarithm of a number from 1 to √2. This is usually done using a rational polynomial. The ratio of the polynomial of the second-order polynomial to the third order is quite good for this.

+15
source

There are several ways to calculate logarithms. See this .

+2
source

Source: https://habr.com/ru/post/916528/


All Articles