Manually implementing atan2 (or atan)

One way is to do it in terms of the Taylor polynomials. Just take the sum to whatever precision you require. Hopefully you wont need to do it often.

Actually, Taylor approximation makes a dog's dinner of arctan. The singular nature of tan gives arctan some very polynomial-unfriendly properties. You could throw in a million terms and I still wouldn't be surprised if things didn't work out.

A much better idea is to use a CORDIC approximation. It's not simple enough to describe here, or particularly well-documented on the web, but you should be able to get by.

If you need something simpler, and are only working to a few decimal places then an interpolated lookup table would do a pretty good job. Arctan's derivative changes as 1/x², so all the interesting stuff happens pretty close to the origin.

I haven't tested it, but I think you'd get sterling performance with a piecewise-linear approximation in intervals uniformly distributed according to log₂(x).

Admiral

Quote:

Original post by TheAdmiral Actually, Taylor approximation makes a dog's dinner of arctan. The singular nature of tan gives arctan some very polynomial-unfriendly properties. You could throw in a million terms and I still wouldn't be surprised if things didn't work out. A much better idea is to use a CORDIC approximation. It's not simple enough to describe here, or particularly well-documented on the web, but you should be able to get by.

You're quite right, I had hoped someone would come in and post a better method - my specialty is in the purer sides of maths. The more useless it is the more I enjoy it. But there were only zero replies so I thought I would post something.

Quote:

If you need something simpler, and are only working to a few decimal places then an interpolated lookup table would do a pretty good job. Arctan's derivative changes as 1/x2, so all the interesting stuff happens pretty close to the origin. I haven't tested it, but I think you'd get sterling performance with a piecewise-linear approximation in intervals uniformly distributed according to log2(x). Admiral

Thats a good idea. I did that once for a project save it was with arcsin and arccos and I generated the table during initialization from the Taylor polynomials and then further used linear approximation to improve accuracy.

Actually, arcsin has a much better Taylor series approximation. would it not be sufficient to write arctan in terms of arcsine (assuming you restrict/nudge the domain appropriately)?

[Edited by - Daerax on March 29, 2007 10:00:41 PM]

Generally, Taylor's series are not good choices for approximating functions that need a _global_ bound on the error. The series are, by definition, good approximations locally. As you move away from the point of expansion, the number of required terms of the series to keep the error bounded increases.

What is generally better is to use least-squares-like approximations based on integral norms. Apparently, such approximations seem to have become lost with time. Look at

@book{Abramowitz:1965,
author = "Milton Abramowitz and Irene A. Stegun",
title = "Handbook of Mathematical Functions with Formulas, Graphs, and
Mathematical Tables",
publisher = "Dover",
address = "New York",
year = "1965"
}

I have various implementations at my Geometric Tools website of the fast approximations found in this book. In particular, look at the fast atan approximations. Incorportaing these into a fast atan2 is relatively painless.

CORDIC algorithms were developed for hand calculators, specifically designed for hardware. Yes, you can implement them in software, but it is my opinion that the least-squares-like approximations are easy to implement, fast, and give good approximations.

Thanks for all the posts!

I've found this algorithm on another site:


It seems to work well enough for what I'm using it for, and is fast. No idea how it works, though. [sad]

[Edited by - benryves on March 30, 2007 5:20:59 AM]

Quote:

Original post by benryves It seems to work well enough for what I'm using it for, and is fast. No idea how it works, though. [sad]

In the case x >= 0d in the posted code, think of z = y/x. Plot the graph of the function f(z) = tan^{-1}(z). It is an s-shaped curve, symmetric through the origin, and is asymptotic to pi/2 as z approaches infinity and asymptotic to -pi/2 as z approaches -infinity. Now plot the graph of the function g(z) = (pi/2)*z/(1+|z|). It is also s-shaped, symmetric through the origin, and has the same asymptotes. The maximum error for z > 0 occurs when the derivative of the function h(z) = f(z) - g(z) is zero. Setting h'(z) = 0 leads to a quadratic equation with roots (approximately) z = 0.313436 and z = 3.19044. At those points, |h(z)| is approximately 0.0711 radians, which is slightly larger than 4 degrees. The website you linked to mentions this maximum error.

Quote:

Original post by Dave Eberly Look at [Abramowitz and Stegun]

Their handbook has been available on the web for a few years now, so looking at it is as simple as going here: http://www.convertit.com/Go/ConvertIt/Reference/AMS55.ASP