Optimizing Memory Allocation in a Simple, but Long Function

[Derek Klinge]

A couple thoughts. I think my original approach would be faster than binary
search for finding the minimum value of N needed to get a decimal level of
absolute accuracy from Euler's number. Here is my reasoning:
EulerlersNumber(13).LimitMethod() - math.e < .1 and
EulersNumber(135).LimitMethod - math.e < .01. N increased by a little more
than a factor of 10. My method would use 130, 131, 132, 133, 134, and 135
as guesses after 13. Using the double + binary search the guesses would be
26, 52, 104, 208, 156, 130, 143, 137, 134, 136, and then 136 after using
the information that n=13 gives an tolerance of < .1. If the trend holds,
then to get the next decimal of accuracy, you would need to do less than 10
searches each time. When I was using my linear approximation method I found
that I never had to do more than 10 additional guesses of N to get the next
digit of accuracy. When I was using EulersMethod() I found this trend held
for as long as I would allow my computer to do the calculations (though
accuracy to 10**-10).

What I find very interesting is that although the limit method is
mathematically equivalent to the linear approximation method, they give
different results, given sufficiently high values of N (at least in
Python). The limit method does not follow my predictions as accurately,
which leads to the question of whether or not the phenomenon I observed was
an artifact of rounding error or not.

Also, my explicit goal is to be able to handle large numbers of N, and to
reduce rounding error to a minimum. Using the fractions module to perform
the limit method with rational numbers rather than binary represented
decimals and got an error that the integer was too long to convert to float
and even when using smaller values of n (10**14) I seem to get values that
are not the same as when using decimals. It seems to me (I'm just thinking
about this at a low level and haven't written out any math to justify it
yet) that because the linear approximation method only multiplies and adds
the rounding error is smaller than in the limit method where numbers are
being taken to exponents that have rounding errors.

Although I see the value of relative error, I am just as interested in
absolute error (though admittedly they are directly related values).

Are there modules or libraries I can/should use to minimize rounding error
and use very large values of N and get an accurate answer? How does the
math module calculate the vale of e?

Thanks,
Derek

On Mon, Apr 25, 2016 at 6:49 AM Oscar Benjamin <oscar.j.benjamin at gmail.com>
wrote:

> On 25 April 2016 at 08:39, Gregory Ewing <greg.ewing at canterbury.ac.nz>
> wrote:
> > Derek Klinge wrote:
> >>
> >> Also, it seems to me if the goal is to use the smallest value of n to
> get
> >> a
> >> particular level of accuracy, changing your guess of N by doubling seems
> >> to
> >> have a high chance of overshoot.
> >
> >
> > If you want to find the exact n required, once you overshoot
> > you could use a binary search to narrow it down.
>
> Also you can calculate the truncation error for Euler's method. Since
>
>    f(t) = f(t0) + f'(t0)*(t - t0) + (1/2)f''(t0)*(t - t0)**2 + O((t -
> t0)**3)
>
> Euler's method just uses the first two terms so
>
>     x[n+1] = x[n] + dt*f(x[n])
>
> the next term would be
>
>    (1/2)*f'(x[n])*dt**2
>
> Since in your case f'(x) = x and dt = 1/N that's
>
>     (1/2)*x[n]*(1/N)**2
>
> As a relative error (divide by x[n]) that's
>
>     (1/2)*(1/N)**2
>
> Let's add the relative error from N steps to get
>
>     N*(1/2)*(1/N)**2 = 1/(2*N)
>
> So the relative error integrating from 0 to 1 with N steps is 1/(2*N).
> If we want a relative error of epsilon then the number of steps needed
> is 1/(2*epsilon).
>
> That is to say that for a relative error of 1e-4 we need N =
> 1/(2*1e-4) = 1e4/2 = 5e3 = 5000.
>
> >>> import math
> >>> N = 5000
> >>> error = math.e - (1 + 1.0/N)**N
> >>> relative_error = error / math.e
> >>> relative_error
> 9.998167027596845e-05
>
> Which is approximately 1e-4 as required.
>
> --
> Oscar
> --
> https://mail.python.org/mailman/listinfo/python-list
>