Algorithm used to calculate approximation of exp, log, ...
projetmbc
what are the algorithms used to calculate approximation of exp ?
Best regards.
Fredrik Johansson
> Hello,
> what are the algorithms used to calculate approximation of exp ?
A few different algorithms, depending on the precision and the argument.
Typically, a two-stage argument reduction is used, followed by
evaluation of the Taylor series.
For example, to evaluate exp, we first write x = y + z*log(2). This
gives exp(x) = exp(y) * 2^z, where we now may take y to be small
(between 0 and log(2)).
Next, we replace y by y / 2^r for some integer r approximately equal
to the square root of the precision. This speeds up convergence of the
Taylor series. We recover exp(y) by computing exp(y / 2^r)^(2^r) using
r squarings.
To evaluate the Taylor series, we use a technique called modular
splitting, baby-step/giant-step summation, or concurrent summation, to
reduce the number of multiplications. Introducing another small
integer parameter u, we write
c[0] + c[1]*x + c[2]*x^2 + ... as
(c[0] + c[u]*x^u + c[2u]*x^(2u) + ...) +
x*(c[1] + c[u+1]*x^u + c[2u]*x^(2u) + ... ) +
... +
x^(u-1)*(c[u-1] + c[2u-1]*x^u + ...)
Most of the arithmetic is done using fixed-point numbers since this
has very little overhead.
Actually, another improvement is used as well: using the Taylor series
for cosh instead of exp, we only need to add half as many terms (for
the cost of an extra square root).
The ideas for log, cos/sin and atan are similar: argument reduction to
a standard interval, argument reduction to accelerate convergence,
followed by Taylor series evaluation.
There are some differences: the second stage of argument reduction for
log and atan is expensive since it involves square roots instead of
multiplications, so it is cheaper to use a precomputed lookup table at
low to medium precision. At extremely high precision, log is computed
using the arithmetic-geometric mean, and atan is computed using Newton
iteration.
There is an excellent book "Modern Computer Arithmetic" by Richard
Brent and Paul Zimmermann where these algorithms and others are
described. A free PDF of a preliminary version of the book is
available here:
http://www.loria.fr/~zimmerma/mca/pub226.html
Fredrik
Christophe BAL
Best regards.
Christophe
Fredrik
--
You received this message because you are subscribed to the Google Groups "mpmath" group.
To post to this group, send email to mpm...@googlegroups.com.
To unsubscribe from this group, send email to mpmath+un...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/mpmath?hl=en.