8
$\begingroup$

Context: I had to write a code that would compute $\arctan(x)$ for all real $x$ with an error less than $10^{-6}$. The only algorithm I could think of was using the Taylor series of $\arctan(x)$, which required a lot of terms to achieve the desired accuracy. I couldn't find any better methods through simple googling, but I 'm sure there are more efficient algorithms for calculating $\arctan$ than the Taylor series.


My question is: Are there any websites or books that collect the best known algorithms for computing all mathematical functions like Special functions, trigonometric functions, transcendental functions, etc.? If no such reference exist then how to find efficient algorithms for mathematical functions?

$\endgroup$
15
  • $\begingroup$ If $x$ is small the Taylor series works. If $x$ is large you can use the Taylor series of $\text{arccot}$. And if $x$ is close to $1$ you can use the Taylor series centered at $1$. That should work okay and presumably other tricks can be applied. $\endgroup$ Commented Jun 21 at 3:38
  • 3
    $\begingroup$ One of my favorite books Numerical Recipes recommends the Padé approximation, which is a ratio of polynomials. It has the advantage that it can fit functions with poles as well as zeros. This doesn't matter for arctan but it does for other functions. Even the innocuous $\frac 1{x^2+1}$ benefits because of the poles off the real line. The function is its own Padé approximation. $\endgroup$ Commented Jun 21 at 4:20
  • 3
    $\begingroup$ A&S = Abramowitz and Stegun offers a bunch of approximations for this and that. $\endgroup$
    – m-stgt
    Commented Jun 21 at 6:06
  • 3
    $\begingroup$ Closely related question for which I provided a fairly detailed answer. $\endgroup$
    – njuffa
    Commented Jun 21 at 17:38
  • 2
    $\begingroup$ Also check out en.wikipedia.org/wiki/CORDIC for a discussion of the ingenious algorithms used for computing trigonometric functions and their inverses using CPUs of very limited capability. $\endgroup$ Commented Jun 21 at 21:10

4 Answers 4

5
$\begingroup$

You could have started at this Wikipedia page. In particular, the simplest approach given under "Elementary functions" is already good enough, namely Taylor series and argument reduction and Newton-Raphson inversion. The point is that you can compute $\exp$ using Taylor series and argument reduction, and you can also compute $\cos,\sin,\tan$ using $\exp$, and you can compute all their inverses using Newton-Raphson.

$\endgroup$
4
  • $\begingroup$ It's actually more efficient to compute log & the inverse trig functions using AGM (arithmetic-geometric mean) based algorithms (which tend to converge quadratically), especially when high precision is required. And then use Newton-Raphson to compute exp & the forward trig functions. See the Carlson refs I linked on the question. The Borweins & Brent have also written on AGM algorithms. $\endgroup$
    – PM 2Ring
    Commented Jun 22 at 7:57
  • $\begingroup$ @PM2Ring: That's why I said "good enough". Beginners should start with simple methods... $\endgroup$
    – user21820
    Commented Jun 22 at 14:05
  • $\begingroup$ Fair enough. It takes fairly sophisticated mathematics to show that the AGM-related algorithms actually do what they're supposed to do. OTOH, the algorithms are pretty easy to implement, especially An algorithm for computing logarithms and arctangents, assuming you don't mind calculating a few square roots. $\endgroup$
    – PM 2Ring
    Commented Jun 22 at 14:39
  • $\begingroup$ @PM2Ring: Sure, AGM is easy to implement (as long as we use sufficient precision)! But you see, the asker said "how to find..."... =) $\endgroup$
    – user21820
    Commented Jun 23 at 13:23
5
$\begingroup$

These are the best books on the subject that I know:

Jean-Michel Muller: "Elementary Functions: Algorithms and Implementation

Jean-Michel Muller et. al: "Handbook of Floating-Point Arithmetic

$\endgroup$
1
$\begingroup$

Books

  • Numerical Recipes: The Art of Scientific Computing by William H. Press, Saul A. Teukolsky, William T. Vetterling, and Brian P. Flannery: is a guide to numerical methods and algorithms, including those for computing many mathematical functions.

  • Handbook of Mathematical Functions by Milton Abramowitz and Irene A. Stegun (referred to as Abramowitz and Stegun): is a classic reference book containing a vast amount of information on mathematical functions, including detailed descriptions, properties and algorithms for computing them.

  • Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables by Frank W. J. Olver, Daniel W. Lozier, Ronald F. Boisvert, and Charles W. Clark (or the NIST Handbook of Mathematical Functions), which is an updated version of Abramowitz and Stegun's book and provides extensive info on mathematical functions and modern numerical methods for computing them.

  • Special Functions by George E. Andrews, Richard Askey, and Ranjan Roy, which covers a wide range of special functions, providing both theoretical background and computational techniques.

  • Computation of Special Functions by Shanjie Zhang and Jianming Jin, which focuses specifically on the computation of special functions, with detailed algorithms and practical implementations.

Other sources:


CORDIC:

For efficiently calculating arctan(), you can use CORDIC:

import math


def _arctan(x, y, it=20):
    atan_table = [math.atan(2 ** (-i)) for i in range(it)]
    z = 0.0
    pow_2 = 1.0

    for i in range(it):
        if y > 0:
            xx = x + y / pow_2
            yy = y - x / pow_2
            z += atan_table[i]
        else:
            xx = x - y / pow_2
            yy = y + x / pow_2
            z -= atan_table[i]

        x, y = xx, yy
        pow_2 *= 2.0

    return z


x, y = 1.0, 0.5
res = _arctan(x, y)
print(f"arctan({y}/{x}) = {res}")


Prints

arctan(0.5/1.0) = 0.4636494681826186
$\endgroup$
1
  • 1
    $\begingroup$ The code is incorrect. arctan(1/2) = 0.463... $\endgroup$
    – qwr
    Commented Jun 22 at 4:42
1
$\begingroup$

If you want to produce your own approximation of $\tan^{-1}(x)$, you just to focus on $x \in \left(0,1\right)$ since $$\tan ^{-1}(x)+\tan ^{-1}\left(\frac{1}{x}\right)=\frac \pi 2$$

Better than Taylor series, consider the $[2n+1,2n]$ Padé approximants $P_n$ which write $$P_n=x \frac {1+\sum_{k=1}^n a_n\, x^{2n}}{1+\sum_{k=1}^n b_n\, x^{2n}}$$ such as $$P_2= x\, \frac{ 1+\frac{7 }{9}x^2+\frac{64 }{345}x^4 } { 1+\frac{10 }{9}x^2+\frac{5 }{21}x^4}$$ whose error is $\frac{64}{43659} x^{11}$; the maximum error is at the upper bound $\frac{\pi }{4}-\frac{436}{555}=1.87422\times 10^{-4}$. To give an idea of the accuracy, the table below reports the infinite norm $$\Phi_n=\int_0^1\big(\tan^{-1}(x)-P_n\big)^2\, dx$$ as well as the maximum error $$\left( \begin{array}{ccc} n & \Phi_n & \text{maximum error} \\ 1 & 3.45766\times 10^{-6} & 6.26850\times 10^{-3} \\ 2 & 2.06378\times 10^{-9} & 1.87422\times 10^{-4} \\ 3 & 1.36438\times 10^{-12} & 5.56331\times 10^{-6} \\ 4 & 9.55466\times 10^{-16} & 1.64573\times 10^{-7} \\ 5 & 6.94592\times 10^{-19} & 4.86014\times 10^{-9} \\ 6 & 5.18365\times 10^{-22} & 1.43393\times 10^{-10} \\ 7 & 3.94436\times 10^{-25} & 4.22828\times 10^{-12} \\ 8 & 3.04669\times 10^{-28} & 1.24678\times 10^{-13} \\ \end{array} \right)$$

In terms of computer resources, these are very cheap using Horner's method (you need only one evaluation of $x^2$).

For example $$P_4=x \, \frac {\left(\left(\left(\frac{16384 x^2}{3828825}+\frac{1289}{7735}\right) x^2+\frac{83}{85}\right) x^2+\frac{91}{51}\right) x^2+1 } {\left(\left(\left(\frac{63 x^2}{2431}+\frac{84}{221}\right) x^2+\frac{126}{85}\right) x^2+\frac{36}{17}\right) x^2+1 }$$

The other, non negligible, aspect, is that all coefficients $(a_n,b_n)$ are positive (no loss of accuracy by subtraction).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .