How to change double sum to be computed in manageable time?
2 views (last 30 days)
Show older comments
Hello.
I am trying to find efficient solution for computation of double sum. To be more specific I have algorithm like following.
i=1:X;
for j=1:Y
A(j) = sum(f1(i).^j); %f1() is some function
end
Result=sum(A);
The above is the idea that is working. However since my Y=100K or so and X=10K the computation is taking so long. Moreover, I would need to do the computation for diferent Y=1:100K and observe the results. That's way too impossible with this approach.
Can anyone give me suggestions how to do this task in real time?
0 Comments
Answers (2)
Star Strider
on 19 Mar 2014
Edited: Star Strider
on 19 Mar 2014
Unless you have a specific reason for storing the A vector, one way to speed it up might be:
i=1:X;
A = 0;
for j=1:Y
A = sum(f1(i).^j) + A; %f1() is some function
end
Result = A;
The reason is that for each new value for A(j), MATLAB has to allocate and fill a new memory location. This takes time. You might be able to get around this by preallocating the A vector if you need to save it for use later in your program by putting:
A = zeros(size(Y));
in place of the A = 0; line, and using the code you posted with A(j) defined in every step of the loop.
( NOTE: it’s best not to use i and j as loop indices because MATLAB uses them for its imaginary operators. Using them as loop indices could confuse things. )
4 Comments
Roger Stafford
on 19 Mar 2014
Your addition is in the wrong order, Peter. If you do the summation with respect to j first, you can take advantage of a formula for the sum of a geometric series and avoid actually doing the summation. The formula is:
a^1 + a^2 + a^3 + a^4 + ... + a^n =
(a-a^(n+1))/(1-a)
which certainly saves a lot of additions. Hence your code could be:
F = f1(1:X);
Result = sum((F-F.^(Y+1))./(1-F));
You will notice that this form also avoids evaluating f1(i) for the same i repeatedly instead of just once.
There is one problem however. You state that Y can be as large as 100000. To avoid overflow to infinity or underflow to zero in matlab's 'double' numbers, the values produced by f1 need to be extremely close to 1, and this will lead to substantial loss of accuracy in the above formula because you will be subtracting two quantities which are very close to each other in the denominator, 1-F.
I can conceive of a compromise between adding 100000 numbers on the one hand and suffering large errors on the other, by using the above formula for, say, every 100 values and adding the resulting 1000 values, or some such strategy.
See Also
Categories
Find more on Logical in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!