Search All of the Math Forum:

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

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

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

 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 10:29 AM

On Oct 19, 3:40 pm, Tim Norfolk <timsn...@aol.com> wrote:
> On Oct 19, 8:39 am, Knud Thomsen <sa...@kt-algorithms.com> wrote:
>
>
>

> > 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- Hide quoted text -

>
> > - Show quoted text -
>
> But my analysis shows that optimizing on your C must thus be better
> than C=n. Hence, your error is at most 1/pe.

Yes, C=Copt gives, as listed in my last table, a max. |abs. error|
that is only about half of that for C=p.
As an example, for p=8192 I get:

E(C=Copt) ~ 1.533993E-5
E(C=p) ~ 3.303950E-5
1/(pe) ~ 4.490716E-5

Regards,
Knud

Date Subject Author
10/15/10 sales@kt-algorithms.com
10/15/10 Timsn274
10/15/10 sales@kt-algorithms.com
10/18/10 Timsn274
10/19/10 sales@kt-algorithms.com
10/19/10 Timsn274
10/19/10 sales@kt-algorithms.com