Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math

Topic: A series of progressively better approximations to exp(-x), x>=0
Replies: 6   Last Post: Oct 19, 2010 10:29 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
sales@kt-algorithms.com

Posts: 78
Registered: 1/29/05
Re: A series of progressively better approximations to exp(-x), x>=0
Posted: Oct 19, 2010 8:39 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

On Oct 19, 3:11 am, Tim Norfolk <timsn...@aol.com> wrote:
> On Oct 15, 1:02 pm, Knud Thomsen <sa...@kt-algorithms.com> wrote:
>
>
>

> > On Oct 15, 3:39 pm, Tim Norfolk <timsn...@aol.com> wrote:
>
> > > On Oct 15, 8:48 am, Knud Thomsen <sa...@kt-algorithms.com> wrote:
>
> > > > Consider approximations of the form, x>=0, p an integer:
>
> > > >                  C                1
> > > >   exp(-x)  ~  (-----)^p  =  -------------             (1)
> > > >                C + x        (1 + 1/C x)^p

>
> > > > The complexity of the approximations is arguably independent of p,
> > > > with only one optimizable constant. Execution time grows as
> > > > O(log(p)) using exponentiation by squaring; then p being a power of
> > > > 2 is particularly efficient.

>
> > > > Note that substituting variable x, e.g. with x^2/2 to create an
> > > > approximation to the Gaussian, does not change the maximum
> > > > |abs. error|.

>
> > > > With an optimal C-value, Copt, the maximum |abs. error| becomes
> > > > roughly inversely proportional to p.

>
> > > > A simple asymptotic approximation to Copt is: C(p) = p-0.6627435.
>
> > > > The following approximation might be useful for precalculation of
> > > > Copt(p):

>
> > > >   Copt(p) ~ Cappr(p) = p - Q0 + Q1/p - Q2/p^2 + Q3/p^3 - Q4/p^4
>
> > > >   Q0 = 0.6627435  Q1 = 0.2569148  Q2 = 0.0772350  Q3 = 0.0157493
> > > >   Q4 = 0.0009863

>
> > > > with an |abs. error| < 9E-7.
>
> > > > In the table below, giving relevant parameters for selected values
> > > > of p, the following abbreviations are introduced:

>
> > > >   Eopt   The max. |abs. error| of appr. (1) for C=Copt
> > > >   Esimp  The max. |abs. error| of appr. (1) for C=p-0.6627435
> > > >   Eappr  The max. |abs. error| of appr. (1) for C=Cappr

>
> > > > ----------------------------------------------------------
> > > >   p          Copt        Eopt       Esimp/Eopt  Eappr/Eopt
> > > > ----------------------------------------------------------
> > > >     1      0.5316985   1.018926E-1   2.1001687   1.0000016
> > > >     2      1.4483130   5.635451E-2   1.3831008   1.0000024
> > > >     3      2.4148834   3.892816E-2   1.2331002   1.0000013
> > > >     4      3.3969007   2.972884E-2   1.1675592   1.0000011
> > > >     5      4.3856753   2.404472E-2   1.1307883   1.0000022
> > > >     6      5.3780032   2.018465E-2   1.1072508   1.0000020
> > > >     7      6.3724285   1.739220E-2   1.0908921   1.0000014
> > > >     8      7.3681949   1.527833E-2   1.0788628   1.0000008
> > > >    10      9.3621912   1.229050E-2   1.0623562   1.0000001
> > > >    12     11.3581384   1.028000E-2   1.0515630   1.0000005
> > > >    16     15.3530151   7.745754E-3   1.0383026   1.0000008
> > > >    24     23.3478275   5.187811E-3   1.0252929   1.0000010
> > > >    32     31.3452094   3.899888E-3   1.0188801   1.0000010
> > > >    48     47.3425749   2.605962E-3   1.0125275   1.0000008
> > > >    64     63.3412515   1.956740E-3   1.0093735   1.0000006
> > > >   128    127.3392587   9.800744E-4   1.0046704   1.0000003
> > > >   256    255.3382588   4.904639E-4   1.0023312   1.0000001
> > > >   512    511.3377580   2.453387E-4   1.0011646   1.0000000
> > > >  1024   1023.3375074   1.226961E-4   1.0005821   1.0000000
> > > >  2048   2047.3373820   6.135471E-5   1.0002911   1.0000001
> > > >  4096   4095.3373193   3.067903E-5   1.0001456   1.0000001
> > > >  8192   8191.3372879   1.533993E-5   1.0000728   1.0000001
> > > >  ..
> > > > ->inf   p-0.6627435#   0.1256681/p#  1.0000000   1.0000000
> > > > ----------------------------------------------------------
> > > > #) Using Aitken's delta-squared process on (p-Copt) and (p*Eopt).

>
> > > > Best regards,
> > > > Knud Thomsen
> > > > Geologist, Denmark

>
> > > This specific problem is an old one in approximation theory. Have you
> > > looked at Pade approximants, for example?

>
> > Yes, I'm familiar with Pade approximants and other approaches in my
> > work with mathematical modelling.
> > What I find interesting about the proposed method is the simple
> > scalability.

>
> > Regards,
> > Knud- Hide quoted text -

>
> > - Show quoted text -
>
> If you want simple, why not set $f_n(x) = (1+x/n)^{-n}$ as your $n$-th
> approximant? The maximum error $f_n(x)-exp(-x)$ on $[0,\infty)$ is at
> $x=x_n$, and equal to $x_n exp(-x_n)/n$. This last quantity is bounded
> by $1/ne$.


That would correspond to setting C=p in my terminology.
This results in a measured error profile like this:

------------------------
p E(C=p)/E(C=Copt)
------------------------
1 1.9984982
2 2.0597549
3 2.0864088
...
2048 2.1537360
4096 2.1537941
8192 2.1538230
...
------------------------

Using C=p-0.6627435, as I suggested, while less simple than just C=p,
offers an asymptotically better approximation (see original table).

Regards,
Knud




Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.