Question

i am trying to calculate the Sum of series for: Σ(1/n), n=1, n=inf. (for every natural number n>0, calculate the Sum of 1/n)

i) we want matlab to return the number of loops until Σ(n)-Σ(n-1)=0.

ii) We want to calculate the time that the code needs to end.

since there is no limit in the increment of n, the run time of the code is huge. however, should we use ie symsum(1,n), for n=~10^8, to have an estimate for the Sum number?, if not, how can we calculate the above questions?

Was it helpful?

Solution

I think this is how you can get close to the actual solution. This is by no means a theoritical solution, but it would narrow down your search range by a huge amount. First, some concepts:

  1. The value of the sum of the above series is given by the harmonic number and its value can be approximated to ln(n+1 where n+1 is your iteration number (not n). For example, if you run 10^8 iterations, the sum would be ~ log(10^8-1)=18.420680733952366 and the actual value (i.e. by code) is 18.997896413852555. I know this is a huge difference, but lets take it (At least I don't know any other method).

UPDATE: see the comment on this answer, you can actually add Euler-Mascheroni constant constant for a better approximation).

  1. As the value of sum increases, your precision becomes shorter, the value of the smallest precision can be obtained by eps(sum) i.e. after 10^8 iterations, the value of eps(sum)=3.552713678800501e-15.

  2. The increment at each iteration needs to be calculated and is very simple. At 10^8 iteration, the increment from previous iteration is 1/10^8.

  3. So, what we want is that the number obtained in (3) should be greater than (2). How to obtain the value of sum in (2), either run the code or use method in (1) (I did the latter).

  4. I observed that eps(8)>1e-15. The increment at iteration 10^15 = 10^-15 < eps(8). Therefore, its already impossible to reach 10^15 iterations. Lets try 10^14 iterations. The increment at iteration 10^14 = 10^-14 < eps(64). That means your sum at 10^14 iterations should be less than 64. Is it? Lets check from formula in (1). It is = log(10^14-1) = 32.236191301916627.

  5. So I concluded that at 10^14 iterations, the precision is still big enough, but at 10^15 is not. So the exact iteration number lies in the range 10^14 to 10^15. Well, you can still narrow it down and possibly with some more effort find the exact iteration number. I have shown you the way.

I actually found out the number of iterations when your condition would be satisfied. I calculated it as follows:

eps(33)= 7.105427357601002e-015 (since eps takes the same value from 32 to 63 and your sum will never reach 64, so this is the value of eps you should be dealing with). So you need your increment to be just above this number. Therefore, I decided to have the increment to be 7.1055e-15. We already know that number of iterations lie between 10^14 and 10^15. Therefore, desired number of iterations must be k*10^14 where k is a constant between 1 to 10 (since when k = 10, it essentially becomes 10^15). Solve (1/(k*10^14))=7.1055e-15 (you can go even finer, I decided to stick with 7.1055e-15. I got k=1.407360495390895. Therefore, number of iterations = 1.407360495390895*10^14.

P.S. I could be wrong. Please cross-check. Also, I suggest you to post this in math.stackoverflow. Before that reframe the question such that you are asking for a theoretical solution and you can get much better answers.

OTHER TIPS

There is several aspects to your question:

ad i) Define a loop that starts summing up your 1/n

ad ii) take a loop at the Matlab commands tic and toc

Last but not least: You should compare 1/n with the machine epsilon, in Matlab this is eps in order to abort once your machine cannot even add something relevant to your sum and abort the loop. Depending on the desired accuracy of the sum, you may of course abort earlier, e.g. comparing 1/n with 1e-8 would mean stopping at n = 1e8.

You can just run this code to try whether it runs into any practical boundaries, I believe it is exactly what you are looking for:

N = 1;
oldSum = -1;
mySum = 0;
tic
while oldSum~=mySum
    oldSum = mySum;
    mySum = mySum + 1/N;
    N = N+1;
end
toc
N

On second thought, this may run on forever. If you use this line instead:

 mySum = single(mySum + 1/N);

You can see the results for a datatype with less precision. In 21.5 seconds it reaches 2097153 iterations and terminates.

This can be used to test theoretical approaches.


UPDATE I figured that instead of decreasing the precision, it is possible to increase the stepsize. Here is the code to get an approximation of the number, it should even not be that hard to get the estimated calculation time from this:

N = 1;
oldSum = -1;
mySum = 0;
p=10;
tic
while oldSum~=mySum && N
    oldSum = mySum;
    mySum = mySum + 1/N;
    if N<1e9 % We need to build up till approximately the right number
        N = N+1;
    else % Here the decrease in 1/N is much more significant than the change in epsilon
        N = N+1e8;
    end
end
toc

This code finishes around N = 5.6295e+14 in 19 seconds, of which about 1 second is spent in large increases, and after some quick calculations I think the estimated time to do this would be about:

18 + 1e8 seconds or roughly 3 years.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top