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

Groups > comp.lang.python > #107579

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

Show key headers only | View raw

Actually, I'm not trying to speed it up, just be able to handle a large
number of n.
(Thank you Chris for the suggestion to use xrange, I am on a Mac using the
stock Python 2.7)

I am looking at the number of iterations of linear approximation that are
required to get a more accurate representation.
My initial data suggest that to get 1 more digit of e (the difference
between the calculated and expected value falls under 10**-n), I need a
little more than 10 times the number of iterations of linear approximation.

I actually intend to compare these to other methods, including limit
definition that you provided, as well as the geometric series definition.

I am trying to provide some real world data for my students to prove the
point that although there are many ways to calculate a value, some are much
more efficient than others.

I tried your recommendation (Oscar) of trying a (1+1/n)**n approach, which
gave me very similar values, but when I took the difference between your
method and mine I consistently got differences of ~10**-15. Perhaps this is
due the binary representation of the decimals?

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. I found that I was able to predict
relatively accurately a value of N for achieving a desired accuracy. By
this I mean, that I found that if I wanted my to be accurate to one
additional decimal place I had to multiply my value of N by approximately
10 (I found that the new N required was always < 10N +10).

Derek

On Sun, Apr 24, 2016 at 4:45 PM, Derek Klinge <schilke.60@gmail.com> wrote:

> Actually, I'm not trying to speed it up, just be able to handle a large
> number of n.
> (Thank you Chris for the suggestion to use xrange, I am on a Mac using the
> stock Python 2.7)
>
> I am looking at the number of iterations of linear approximation that are
> required to get a more accurate representation.
> My initial data suggest that to get 1 more digit of e (the difference
> between the calculated and expected value falls under 10**-n), I need a
> little more than 10 times the number of iterations of linear approximation.
>
> I actually intend to compare these to other methods, including limit
> definition that you provided, as well as the geometric series definition.
>
> I am trying to provide some real world data for my students to prove the
> point that although there are many ways to calculate a value, some are much
> more efficient than others.
>
> Derek
>
> On Sun, Apr 24, 2016 at 2:55 PM, Oscar Benjamin <
> oscar.j.benjamin@gmail.com> wrote:
>
>> On 24 April 2016 at 19:21, Chris Angelico <rosuav@gmail.com> wrote:
>> > On Mon, Apr 25, 2016 at 4:03 AM, Derek Klinge <schilke.60@gmail.com>
>> wrote:
>> >> Ok, from the gmail web client:
>> >
>> > Bouncing this back to the list, and removing quote markers for other
>> > people's copy/paste convenience.
>> >
>> > ## Write a method to approximate Euler's Number using Euler's Method
>> > import math
>> >
>> > class EulersNumber():
>> >     def __init__(self,n):
>> >         self.eulerSteps = n
>> >         self.e    = self.EulersMethod(self.eulerSteps)
>> >     def linearApproximation(self,x,h,d): # f(x+h)=f(x)+h*f'(x)
>> >         return x + h * d
>> >     def EulersMethod(self, numberOfSteps): # Repeate linear
>> > approximation over an even range
>> >         e = 1                                                    # e**0
>> = 1
>> >         for step in range(numberOfSteps):
>> >             e = self.linearApproximation(e,1.0/numberOfSteps,e) # if
>> > f(x)= e**x, f'(x)=f(x)
>> >         return e
>> >
>> >
>> > def EulerStepWithGuess(accuracy,guessForN):
>> >     n = guessForN
>> >     e = EulersNumber(n)
>> >     while abs(e.e - math.e) > abs(accuracy):
>> >         n +=1
>> >         e = EulersNumber(n)
>> >         print('n={} \te= {} \tdelta(e)={}'.format(n,e.e,abs(e.e -
>> math.e)))
>> >     return e
>> >
>> >
>> > def EulersNumberToAccuracy(PowerOfTen):
>> >     x = 1
>> >     theGuess = 1
>> >     thisE = EulersNumber(1)
>> >     while x <= abs(PowerOfTen):
>> >         thisE = EulerStepWithGuess(10**(-1*x),theGuess)
>> >         theGuess = thisE.eulerSteps * 10
>> >         x += 1
>> >     return thisE
>> >
>> >
>> >> To see an example of my problem try something like
>> EulersNumberToAccuracy(-10)
>>
>> Now that I can finally see your code I can see what the problem is. So
>> essentially you want to calculate Euler's number in the following way:
>>
>> e = exp(1) and exp(t) is the solution of the initial value problem
>> with ordinary differential equation dx/dt = x and initial condition
>> x(0)=1.
>>
>> So you're using Euler's method to numerically solve the ODE from t=0
>> to t=1. Which gives you an estimate for x(1) = exp(1) = e.
>>
>> Euler's method solves this by going in steps from t=0 to t=1 with some
>> step size e.g. dt = 0.1. You get a sequence of values x[n] where
>>
>>    x[0] = x(0) = 1  # initial condition
>>    x[1] = x[0] + dt*f(x[0]) = x[0] + dt*x[0]
>>    x[2] = x[1] + dt*x[1] # etc.
>>
>> In order to get to t=1 in N steps you set dt = 1/N. So simplifying
>> your code (all the classes and functions are just confusing the
>> situation here):
>>
>> N = 1000
>> dt = 1.0 / N
>> x = 1
>> for n in range(N):
>>     x = x + dt*x
>> print(x)
>>
>> When I run that I get:
>> 2.71692393224
>>
>> Okay that's great but actually you want to be able to set the accuracy
>> required and then steadily increase N until it's big enough to achieve
>> the expected accuracy so you do this:
>>
>> import math
>>
>> error = 1
>> accuracy = 1e-2
>>
>> N = 1
>> while error > accuracy:
>>     dt = 1.0 / N
>>     x = 1
>>     for n in range(N):
>>         x = x + dt*x
>>     error = abs(math.e - x)
>>     N += 1
>> print(x)
>>
>> But what happens here? You have a loop in a loop. The inner loop takes
>> n over N values. The outer loop takes N from 1 up to Nmin where Nmin
>> is the smallest value of N such that we achieve the desired accuracy.
>>
>> This is a classic case of a quadratic performance algorithm. As you
>> make the accuracy smaller you're implicitly increasing Nmin. However
>> the algorithmic performance is quadratic in Nmin i.e. O(Nmin**2). The
>> problem is the nested loops. If you have an outer loop that increases
>> the length of an inner loop by 1 at each step then you have a
>> quadratic algorithm akin to:
>>
>> # This loop is O(M**2)
>> for n in range(N):
>>     for N in range(M):
>>         # do stuff
>>
>> To see that it is quadratic see:
>>
>>     https://en.wikipedia.org/wiki/Triangular_number
>>
>> The simplest fix here is to replace N+=1 with N*=2. Instead of
>> increasing the number of steps by one if the accuracy is not small
>> enough then you should double the number of steps. That will give you
>> an O(Nmin) algorithm.
>>
>>
>> https://en.wikipedia.org/wiki/1/2_%2B_1/4_%2B_1/8_%2B_1/16_%2B_%E2%8B%AF
>>
>> A better method is to do a bit of algebra before putting down the code:
>>
>>     x[1] = x[0] + h*x[0] = x[0]*(1+h) = x[0]*(1+1/N) = (1+1/N)
>>     x[2] = x[1]*(1+1/N) = (1+1/N)**2
>>     ...
>>     x[n] = (1 + 1/n)**n
>>
>> So doing the loop for Euler's method is equivalent to just writing:
>>
>>     x = (1 + 1.0/N)**N
>>
>> This considered as a sequence in N is well known as a sequence that
>> converges to e. In fact this is how the number e was first discovered:
>>
>>
>> https://en.wikipedia.org/wiki/E_%28mathematical_constant%29#Compound_interest
>>
>> Python can compute this much quicker than your previous version:
>>
>> N = 1
>> for _ in range(40):
>>     N *= 2
>>     print((1 + 1.0/N) ** N)
>>
>> Which runs instantly and gives:
>>
>> 2.25
>> 2.44140625
>> 2.56578451395
>> 2.63792849737
>> 2.67699012938
>> 2.69734495257
>> 2.70773901969
>> 2.71299162425
>> 2.71563200017
>> 2.71695572947
>> 2.71761848234
>> 2.71795008119
>> 2.71811593627
>> 2.71819887772
>> 2.71824035193
>> 2.7182610899
>> 2.71827145911
>> 2.71827664377
>> 2.71827923611
>> 2.71828053228
>> 2.71828118037
>> 2.71828150441
>> 2.71828166644
>> 2.71828174745
>> 2.71828178795
>> 2.71828180821
>> 2.71828181833
>> 2.7182818234
>> 2.71828182593
>> 2.71828182719
>> 2.71828182783
>> 2.71828182814
>> 2.7182818283
>> 2.71828182838
>> 2.71828182842
>> 2.71828182844
>> 2.71828182845
>> 2.71828182845
>> 2.71828182846
>> 2.71828182846
>>
>> So your method is computing the above numbers but in a slower way that
>> also has more potential for rounding error. The error here is 1e-13
>> for the last numbers in this sequence. But N=2**40 so your Euler
>> method would need approximately 10**12 iterations in your inner loop
>> to get the same result. That's going to be slow even if you don't use
>> a quadratic algorithm.
>>
>> --
>> Oscar
>> --
>> https://mail.python.org/mailman/listinfo/python-list
>>
>
>

Back to comp.lang.python | Previous | Next — 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