Optimizing Memory Allocation in a Simple, but Long Function
Derek Klinge
schilke.60 at gmail.com
Sun Apr 24 23:58:02 EDT 2016
So I tried the recommended limit approach and got some interesting results.
## Write a method to approximate Euler's Number using Euler's Method
import math
class EulersNumber():
def __init__(self,n):
self.n = n
self.e = 2
def linearApproximation(self,x,h,d): # f(x+h)=f(x)+h*f'(x)
return x + h * d
def EulersMethod(self): # Repeat linear approximation over an even range
e = 1 # e**0 = 1
for step in xrange(self.n):
e = self.linearApproximation(e,1.0/self.n,e) # if f(x)= e**x, f'(x)=f(x)
self.e = e
return e
def LimitMethod(self):
self.e = (1 + 1.0/self.n) ** self.n
return self.e
def SeriesMethod(self):
self.e = sum([1.0/math.factorial(i) for i in range(self.n+1)])
return self.e
I found that the pattern of an additional digit of accuracy corresponding
to 10*n did not hold as strongly for that value (I can post data if
desired). I also got some results that seem to contradict the mathematical
definition. For example try EulersNumber(10**15).LimitMethod(), the
definition places this limit at e, and yet the (python) answer is >3.035.
Please let me know if I've fouled up the implementation somehow.
Also my reasoning for writing this up as a class was to be able to get the
value of n used to generate that value e. If there is some other way to do
that, I'd be happy to try it out.
Thanks,
Derek
Derek
On Sun, Apr 24, 2016 at 8:12 PM, Derek Klinge <schilke.60 at 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.
>
> 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 at 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 at gmail.com> wrote:
>>
>>> On 24 April 2016 at 19:21, Chris Angelico <rosuav at gmail.com> wrote:
>>> > On Mon, Apr 25, 2016 at 4:03 AM, Derek Klinge <schilke.60 at 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
>>>
>>
>>
>
More information about the Python-list
mailing list