Re: Optimizing Memory Allocation in a Simple, but Long Function

From	Oscar Benjamin <oscar.j.benjamin@gmail.com>
Newsgroups	comp.lang.python
Subject	Re: Optimizing Memory Allocation in a Simple, but Long Function
Date	2016-04-25 14:45 +0100
Message-ID	<mailman.76.1461591982.32212.python-list@python.org> (permalink)
References	(8 earlier) <CAGuRns911cXoppsS_8f657UDdCtVFhAzwY7ohafOqrsEuRq7vQ@mail.gmail.com> <CAGuRns9byxLC3pGrkPG8m-qLTzB1+PYxLHNy2=fOHcwWR21x6A@mail.gmail.com> <mailman.63.1461553965.32212.python-list@python.org> <do5vu5Fipb4U1@mid.individual.net> <CAHVvXxTU2k74S_hG=RtsEx=5uTk34Ppf4t2PhqBsat39Kv3ihQ@mail.gmail.com>

Show all headers | View raw

On 25 April 2016 at 08:39, Gregory Ewing <greg.ewing@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

Thread

Re: Optimizing Memory Allocation in a Simple, but Long Function Derek Klinge <schilke.60@gmail.com> - 2016-04-24 20:12 -0700
  Re: Optimizing Memory Allocation in a Simple, but Long Function Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2016-04-25 19:39 +1200
    Re: Optimizing Memory Allocation in a Simple, but Long Function Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2016-04-25 14:45 +0100
    Re: Optimizing Memory Allocation in a Simple, but Long Function Derek Klinge <schilke.60@gmail.com> - 2016-04-25 14:35 +0000
    Re: Optimizing Memory Allocation in a Simple, but Long Function Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2016-04-26 10:54 +0100

csiph-web