Optimizing Memory Allocation in a Simple, but Long Function

[Oscar Benjamin]

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