Path: csiph.com!fu-berlin.de!uni-berlin.de!not-for-mail
From: Oscar Benjamin <oscar.j.benjamin@gmail.com>
Newsgroups: comp.lang.python
Subject: Re: Optimizing Memory Allocation in a Simple, but Long Function
Date: Mon, 25 Apr 2016 14:45:55 +0100
Lines: 55
Message-ID: <mailman.76.1461591982.32212.python-list@python.org>
References: <CAGuRns8KhOFL-a1_a=0hMP=NbktoJw78ih3j4uUSbvkF8bf3pw@mail.gmail.com> <CAPTjJmrQfk20EuoZVMLqKv8F5r=YyKj0nr8iNPw7DWoCEYLmYA@mail.gmail.com> <CAGuRns86c4G5BHX_FF-OBnV_eRVKyngx_Dfp0u7hoHRT0WN++w@mail.gmail.com> <CAPTjJmq5g848-PMTgHOg7sawm+JgA5mSfwDHA-ZZgsmYr6yLCA@mail.gmail.com> <CAGuRns8LsThq3iV-bkdBbg9fZO7s61z4ggBy=YkGDqhaB_J4Xw@mail.gmail.com> <CAGuRns9uvHVBXP79X1Sp8vsW4JpWF-3g1mJoWHOq-cGog61cug@mail.gmail.com> <CAPTjJmpvtP5pj_NiJNXGLmu2QCqSYZNgZjKisRRMRTtzvGHKyQ@mail.gmail.com> <CAHVvXxSwb8=a+b5WQfd3KeXTe8VuL4RMnwu3TSNp8129FJHJGw@mail.gmail.com> <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>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8
In-Reply-To: <do5vu5Fipb4U1@mid.individual.net>
Precedence: list
Xref: csiph.com comp.lang.python:107603

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