From: Joe Keane <jgk@jgk.org>
Newsgroups: sci.math.num-analysis,sci.math.symbolic,sci.misc,comp.arch.arithmetic
Subject: Re: !!! Fastest Sinus & Cosinus algorithms !!!
Date: 30 Apr 1997 18:25:36 -0700
Message-ID: <5k8reg$j1f@shellx.best.com>

In article <E9DKst.KzH@cwi.nl>
Dik T. Winter <dik@cwi.nl> writes:
>Is there a good book that describes approximations by Chebyshev
>polynomials?

I don't know, but i think it's pretty simple.

Assuming x is in [-1,1], let x = cos(t) and your basis functions are 1,
cos(t), cos(2*t), and so on.  Then pick N points equally spaced for t in
[0,pi], where N is 80 or so.  Make a vector of your function values at
these points, and for each basis function, make a vector of the cosines,
correlate the two vectors, and divide by the auto-correlation of the
basis vector, which should be N or N/2.  That gives your coefficients.

Try different sets of points to make sure you get consistent results.
The coefficients should fall off quickly, and you can easily see where
to cut to get the desired accuracy.  Then if you like, you can convert
the sum of cosines back to a polynomial in x.  If your original interval
is far away from zero, do a subtraction at run-time to get the argument
roughly centered at zero, rather than including that in the polynomial.

If the coefficients don't decrease so fast, that means you're too close
to a singularity, and you should use smaller intervals or maybe use an
alternate evaluation.  Using smaller intervals makes the coefficients
fall off much faster, so you have less multiplies at run-time, at the
cost of a larger look-up table, which is a classic trade-off.

Of course you want to do the preceding calculations with high precision,
much more than you'll use at run-time.  I use Emacs Calculator; it's not
super fast but it's convenient and you only have to do this once.

--
Joe Keane, amateur mathematician