How to reduce For loop execution time?

I have following Matlab code to calculate summation of exponential summation term:

This code takes approx. 600 seconds to give final output s. Is there any way to reduce this computation time?

sum1 = 0;
s = 0;
for i=1:1000000000
    for j=1:3
        sum1 = sum1+(i*proc(j))^2;
    end
        s = s+exp(-sum1);
end

[Walter Roberson]

We recommend that you do not use sum as the name of a variable, as it interferes with using the common function sum() . It is quite common that when sum is used as a variable name, that at some point the user will also want to use sum() as a function.

[Ajinkya Bankar]

Thank you for the suggestion. Let me change the name of the variable as sum1. But still the same problem happens for execution time. Please suggest some solution.

[Rik]

At least you can replace your inner loop (assuming proc(j) returns the same output every time it is called with the same input). But I don't see an easy way to replace the outer loop. Can you confirm this is the way your code should work? Because it would be a lot easier if sum1 would be set to 0 inside the outer loop.

[Walter Roberson]

Godo point, Rik. The code I posted does do the equivalent of assuming that sum1 is set to 0 inside the outer for loop.

[Ajinkya Bankar]

I can not make sum1 as 0 inside the outer for loop. That gives wrong result.

[Steven Lord]

What is the mathematical (not code) expression of what you're trying to compute with this code? Or do you have a description in words of what you're trying to compute? That might help us understand what the right result is and find an efficient way to compute that right result.

Also, what are the contents of the variable proc? When you get to the last iterations of the outer loops, you're adding an extremely large number to sum1 unless the elements of proc are very small. You might be able to stop the outer loop sooner if sum1 is so large that exp(-sum1) underflows to 0.

y = 750;
exp(-y) % 0

[Ajinkya Bankar]

I apologize for my mistake. I interpreted the equation in wrong way. sum1 should be 0 inside outer for loop. Thank you everyone for your help and suggestions.

Answer 1

[Walter Roberson]

>> tic;s = sum(exp(-sum((reshape(proc(1:3), [], 1) * (1:1000000000)).^2))); toc
Elapsed time is 55.136908 seconds.

This was slowed down a fair bit because I ran out of memory and it started to swap. On my system, if I had run it in 10 sections of 1E8 the time would have been less than 20 seconds.

[Ajinkya Bankar]

This logic gives me wrong answer. Is there any other way? Kindly suggest.

[Walter Roberson]

It would probably need a cumsum() in there somewhere but I am not sure where at the moment.

[Ajinkya Bankar]

Thank you for the help. When I am trying to increase the outer loop to 10000000000, I get following error.

Requested 10000000000x1 (74.5GB) array exceeds maximum array size preference. 
Creation of arrays greater than this limit may take a long time and cause MATLAB to 
become unresponsive. See array size limit or preference panel for more information.

[Walter Roberson]

As I said, "This was slowed down a fair bit because I ran out of memory and it started to swap." That was with 1E9. With 1E10 the swapping would be worse.

It might make sense to break it into sections 1E8 large.

However, using 3 randn values for p, I find that using just the range 1:9 is sufficient to account for all of the bits of the result. As Steven Lord points out, the values in proc would have to be very small to make it worth doing more than a few iterations.

[Ajinkya Bankar]

Yes, the values in proc are very very small. Therefore, I need to execute outer for loop more times.

proc = [2.89836435405037e-13, 1.14346678029400e-12, 4.58424445869020e-13]

[Walter Roberson]

I notice that the contribution of each element does not go down to eps until you reach 4743809974903 which is greater than 2^42. Even if you break it up into segments to avoid memory overflow, that is a lot of calculations. If we approximate being able to do 2^30 values per second (e.g., 3-ish GHz CPU and suppose somehow it only took 3 clock cycles per value) then it would take 2^12 = 4096 seconds. My measured speed on my system is more on the order of 4.6E-8 seconds per iteration, approximately 218215 seconds = about 60 hours.