Re: Efficiency of math.h

From: Christian Bau (christian.bau_at_cbau.freeserve.co.uk)
Date: 02/26/04 

Date: Wed, 25 Feb 2004 23:08:02 +0000

In article <403D0A18.5030204@jpl.nasa.gov>,
 "E. Robert Tisdale" <E.Robert.Tisdale@jpl.nasa.gov> wrote:

> CBFalconer wrote:
>
> > Peter Ammon wrote:
> >
> > ... snip ...
> >
> >>Why not get libm from GNU and find out? I wouldn't be surprised
> >>if you could beat acos() with "good enough" precision over a
> >>particular range (whatever you're interested in).
> >>Try using a Taylor expansion.
> >
> > Not if you want speed you don't.
> > With some slight trigonometry,
> > you should be able to convert cos(angle) into tan(angle).
> > Use this as input to an arctan(value) routine,
> > which can in turn be built in various ways.
> > One uses a leveled Tschebychev approximation over 0 to 1.
>
> Not if you want speed you don't.
>
> This method requires reading a bunch of high precision
> floating-point numbers from system memory
> which can actually require more time than computing
> Taylor coefficients in registers on-the-fly.
>
> You're out of your depth here Chuck.

Tisdale, you are clueless. As usual.

The fastest approach would be to split the argument range into two
parts, abs (x) <= c and abs (x) >= c for some suitably chosen c,
probably somewhere around 0.7 or 0.8. For abs (x) <= c, approximate acos
x by a polynomial of the form (pi - ax - bx^3 - cx^5...). For x > c,
define f (z) = acos (1 - z^2). Appromiate f (z) by a polynomial of the
form ax + bx^3 + cx^5 + dx^7. Calculate acos (x) = f (sqrt (1-x)). For x
< -c use acos (x) = pi () - acos (-x) = pi () - f (sqrt (1+x)). Take a
higher polynomial depending on how much precision you want. Finding the
coefficients is left as an exercise to the reader :)

The substitution z = sqrt (1-x) nicely catches the behavior of acos x
for abs (x) close to 1, where the first derivative is unbounded and
avoids excessive rounding errors.

Relevant Pages