What is the fastest known algorithm for calculating the sin(x) or
cos(x) or ln(x) functions, suitable for implementing in a
microprocessor?

Or, what is the one, used in Pentium or PowerPC or some really fast
DSP? Because such info may not be publicly available, at least what
and how many computations does it take? (Comparision tables, etc.)

Or, where (paper or inet) can I learn about such algorithms for fast computations?

---

Request for Question Clarification by tox-ga on 30 May 2004 01:34 PDT

Hi shashko,

Do you know if you will have a hardware multiplier available?  If so,
the answer may turn out to involve sophisticated table-lookup or power
series approximation algorithms.

If not, or if you would like to save the gates required to implement a
hardware multiplier, I could provide you with a wealth of information
on iterative solutions that do not require multipliers.  These
algorithms form a well researched field of electrical
engineering/computer science and many are available in the public
domain.

Generally, microprocessors will have a hardware multiplier (Pentium
and PowerPC included) and so will most DSP microprocessors.  However,
in the field of DSP, the iterative methods are sometimes preferred to
save gates an sometimes time.  Many feel that they are required for
truly intensive signal processing.

Answering this question and perhaps giving any further context to your
inquiry will aid in providing a good answer.

Best regards,
tox-ga

---

Request for Question Clarification by mathtalk-ga on 06 Jun 2004 14:34 PDT

Hi, shashko-ga:

A microprocessor itself, if it computes elementary transcendental
functions at all, does so over restricted ranges.  A high-level
implementation (such as from within a C compiler, for example) takes
advantage of the low-level machine instructions by combining range
reduction operations with calls to those simplified microprocessor
instructions.

In the specific case of the sine and cosine functions, one might
implement only the restricted range [0,pi/4] for both, because other
argument ranges are quite easily "mapped" to this one.  For example,
the sine and cosine functions are periodic (of period 2pi), so any
argument can be reduce to one in the range from -pi to +pi (for either
function).  The sine function is odd and the cosine function even, so
in either case the functions' values on [-pi,0] are trivially related
to those on [0,+pi].  Further reduction to [0,pi] would be based on
the standard formulas for supplementary and complementary angles, e.g.

cos(pi - x) = - cos(x)

cos(pi/2 - x) = sin(x)

In the case of logarithmic functions the range reduction would be most
naturally carried out by "scaling" with powers of two (assuming a
binary arithmetic format) to restricted range [1,2].  For example:

ln(x * 2^n) = ln(x) + n * ln(2)

allows this sort of range reduction to be carried out directly from
the inspection of the binary "exponent" of floating point values.

If you wish, I'm sure that for a specific microprocessor, a Researcher
would be able to supply you with the details of what restricted range
instructions are implemented by those units.

On the other hand the phrasing of your Question seems to be open to a
broader interpretation, asking for more details of how such machine
instructions are themselve implemented "in a microprocessor".  I
believe a great deal of information could be provided for you,
whichever area is the one your are interested in, but a better Answer
can be prepared if we know a bit more clearly what you would like.

regards, mathtalk-ga

These might provide a starting point for you.

The Computation of Transcendental Functions on the IA-64 Architecture
http://developer.intel.com/technology/itj/q41999/pdf/transendental.pdf
By exploiting some of the key features of the IA-64 floating-point
architecture, we have been able to provide double-precision
transcendental functions that are highly accurate
yet can typically be evaluated in between 50 and 70 clock
cycles.

http://www.cse.iitd.ernet.in/~dheerajb/perfmetrics.pdf
Rules for Counting Floating-Point Operations (NAS standards)
...
A sine, exponential, etc. is counted as 8 flop

Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd Edition)
by Donald E. Knuth
http://www.amazon.com/exec/obidos/tg/detail/-/0201896842

IA-64 and Elementary Functions: Speed and Precision
By Peter Markstein.
http://www.phptr.com/title/0130183482

If "in a microprocessor" means implemented within the hardware, the
CORDIC method requires only shifts, adds and lookups from small
tables.  The basic approach takes about one iteration for each bit of
accuracy.  There are complex speed-up techniques published in lots of
papers.

If "in a microprocessor" means implemented in code executed by the
processor, where it is a "modern" processor with a fast multiply or
fast multiply and accumulate instruction, then simple polynomial or
rational polymonial (division of two polynomials) is usually faster.