A couple thoughts. I think my original approach would be faster than binary search for finding the minimum value of N needed to get a decimal level of absolute accuracy from Euler's number. Here is my reasoning: EulerlersNumber(13).LimitMethod() - math.e < .1 and EulersNumber(135).LimitMethod - math.e < .01. N increased by a little more than a factor of 10. My method would use 130, 131, 132, 133, 134, and 135 as guesses after 13. Using the double + binary search the guesses would be 26, 52, 104, 208, 156, 130, 143, 137, 134, 136, and then 136 after using the information that n=13 gives an tolerance of < .1. If the trend holds, then to get the next decimal of accuracy, you would need to do less than 10 searches each time. When I was using my linear approximation method I found that I never had to do more than 10 additional guesses of N to get the next digit of accuracy. When I was using EulersMethod() I found this trend held for as long as I would allow my computer to do the calculations (though accuracy to 10**-10).
What I find very interesting is that although the limit method is mathematically equivalent to the linear approximation method, they give different results, given sufficiently high values of N (at least in Python). The limit method does not follow my predictions as accurately, which leads to the question of whether or not the phenomenon I observed was an artifact of rounding error or not. Also, my explicit goal is to be able to handle large numbers of N, and to reduce rounding error to a minimum. Using the fractions module to perform the limit method with rational numbers rather than binary represented decimals and got an error that the integer was too long to convert to float and even when using smaller values of n (10**14) I seem to get values that are not the same as when using decimals. It seems to me (I'm just thinking about this at a low level and haven't written out any math to justify it yet) that because the linear approximation method only multiplies and adds the rounding error is smaller than in the limit method where numbers are being taken to exponents that have rounding errors. Although I see the value of relative error, I am just as interested in absolute error (though admittedly they are directly related values). Are there modules or libraries I can/should use to minimize rounding error and use very large values of N and get an accurate answer? How does the math module calculate the vale of e? Thanks, Derek On Mon, Apr 25, 2016 at 6:49 AM Oscar Benjamin <oscar.j.benja...@gmail.com> wrote: > On 25 April 2016 at 08:39, Gregory Ewing <greg.ew...@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 > -- > https://mail.python.org/mailman/listinfo/python-list > -- https://mail.python.org/mailman/listinfo/python-list
