2

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?

4
  • I assume that you mean symsum(1/n,1,Inf)? You're not going to get anywhere near the correct answer if you calculate this with double precision (in fact, you'll be infinitely wrong).
    – horchler
    Dec 5, 2013 at 1:00
  • i edited my first post, it was full of syntax errors :D Exactly. that is the main problem. I know how to calculate the Sum (and of course, i am not going to run it). However i still need to find a way to calculate the number of loops (or the increments of n), and I'm not sure how. Dec 5, 2013 at 1:12
  • Updated my post, it seems that if you are really really patient you could actually do this! Dec 5, 2013 at 16:02
  • Actually there is a limit to N if you use a simple loop and simple integer. See this: isequal(1e16,1e16+1) Dec 5, 2013 at 16:10

3 Answers 3

1

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.

1
0

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.

4
  • This is my bad i wasn't clear in my first post. i have a while loop that theorytically calculates everything, but practically its impossible to run. Dec 5, 2013 at 1:13
  • @user1467940: And if you do want to go all the way to eps, you'll need 4,503,599,627,370,496 iterations, i.e. 1/eps (this assumes exact division and addition). In other words this can be solved theoretically without the need of Matlab.
    – horchler
    Dec 5, 2013 at 1:35
  • I am not sure if I understand correctly, you mean 1/eps(1) is the theoritical answer? since we want to reach the larger number represenatble in matlab (not realmax, but the larger), i can not see why 1/eps is equivalent to that Dec 5, 2013 at 1:47
  • 1
    @horchler Σ(n)-Σ(n-1)=0 this condition will occur much before than expected. Because precision will get smaller and smaller as value of sum increases. For example, I ran 10^8 iterations, and the sum= 18.997896413852555. So essentially after 10^8 iterations, precision becomes eps(18.997896413852555)=3.552713678800501e-15. As of now, I don't know how to theoretically calculate the value of n.
    – Autonomous
    Dec 5, 2013 at 2:26
0

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.

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.