Execution time bottleneck: How

[Dik T. Winter]

Numerical mathematics time.

In article <91053.093740ADARTNEL at ESOC.BITNET> ADARTNEL at ESOC.BITNET writes:
 > You may be able to replace the exp function with an approximation,
 >      exp(x) = ( ( ( (x/5+1) * x/4 + 1 ) * x/3 + 1 ) * x/2 + 1 ) * x + 1
 > but this depends on the accuracy you require and the range of values of x.

This requires 4 divisions, 4 multiplications and 5 additions.  Divisions can
be changed to multiplications, than we have 9 multiplications and
5 additions.  The maximal absolute error on (-0.5,0.5) is approximately
2.4e-5.  The code above can be rewritten to use only 5 multiplications and
5 additions.

Now take the following approximation:
    (((0.042190*x+0.169287)*x+0.499951)*x+0.999836)*x+1.0;
4 multiplications and 4 additions.  Maximal absolute error on (-0.5,0.5)
approximately 1.8e-5.  We can change to:
   ((((0.008421*x+0.042190)*x+0.166656)*x+0.499951)*x+1.0)*x+1.0;
with 5 multiplications and 5 additions and a maximal absolute error on
(-0.5,0.5) of approximately 1.5e-6.
But do not use these last two outside the interval.

The BSD 4.3-tahoe code takes (approximately) 1 division, 7 multiplications
and 8 additions to get 56 bit (VAX) precision.  (However that code does
some additional work to allow all arguments that do not result in overflow.)

Magic?  No numerical mathematics.  Using Taylor series almost always leads
to slower routines.
--
No there are no typo's in those coefficients.  I just calculated them.
--
dik t. winter, cwi, amsterdam, nederland
dik at cwi.nl