Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #107603

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

Show key headers only | 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

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

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