Math Forum Discussions

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

Plain Text

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