|Re: Before CORDIC|
Message #4 Posted by Bill Wiese on 4 Feb 2004, 9:02 p.m.,
in response to message #1 by GE (France)
Some processors use Chebyshev polynomials or rational approximations (warped or otherwise) to generate transcendentals. While CORDIC is great for limited hardware it has a fundamental serialization limit and can't really have much work parallelized.
Power series approximations are useful because they only require multiply and add operations (often simplified thru Horner's method & perhaps Estrin's method). But some functions don't have a good fit against polynomials, and rational approximations work better - if division is not painful on your architecture.
Depending on the architecture, this log approx you've mentioned could be fast or slow - it would help if the CPU offered hardware multiply and divide and a square-root primitive. [See J.F. Muller's book or Israel Koren's book - square root, reciprocal square root and division are all about the same complexity.]
The art of doing some of these approximations in conjunction with range reduction algorithms is to not have error (that is, guaranteed monotonicity) across ranges.
If there's a slight error in the result's last bit or digit - which otherwise may well be inconsequential - you can get weird things happening - numerical derivatives (delta F(x)Y/deltaX where x is very small) may give the wrong sign if the two x points cross a range boundary for the range reduction algorithm.
Seems that most modern FP CPUs now run the actual approximation for the transcendental algorithm over a VERY small range (reduces # of coefficients, etc.)
Seems like the goal now for transcendentals is to do the approx. algorithm over a very small, known, predictable range with well-characterized error bounds and then use a good range reduction algorithm and answer rescaling algorithm to compensate.
J.F. Muller's "Elementary Functions" (Elementary Approximations"???) is currently in print and is a good survey of modern technique. Cody & Waite have the classic "Software manual for the Elementary Functions" but it is out of print (great reference, w/FORTRAN examples).
IIRC, Israel Koren's book mostly stays away from transcendentals but deals w/floating point math and square root primitives and gate-level hardware tricks - freaky things like signed-digit and residual number systems, along with Radix-N SRT division (remember the Intel divide bug??)
San Jose CA