MATLAB: Nested for-loops too slow

for loop

Hello,
I'm having trouble to compute a summation with four indices. My code below is very time consuming. The problem is have to compute for every i,j,k,l the three smallest elements of A. Any other suggestions that run a bit faster than my code? (N is approximately 156)
sum = 0;
  for i=1:N
      for j=1:N
          for k=1:N
              for l=1:N
                  A = [N-(i-1),N-(j-1),N-(k-1),N-(l-1)];
                  B = sort(A);
                  sum = sum + B(1)*B(2)*B(3);
              end
          end
      end
  end
Thank you very much!

Best Answer

You might want to work more on that code manually before implementing it like that. As the only thing that really matters is N, I think it should be possible to derive a more closed-form formula for the total sum and at least it should be possible to reduce the number of iterations by factoring out some constants.
E.g. I note [i,j,k,l] as your complete index: going from [1,1,1,1] to [1,1,1,X], you know what the results will be for any X (larger than 1): you already know the smallest values so you are wasting time iterating of all other values, sorting, multiplying and summing while you could just see that in that case you can add (N-1) * 1 * 1 * 1
Also remember that your case is quite symmetric towards your indexes: [i,j,k,l] will produce the same output as e.g. [j,i,k,l] and [i,j,l,k] (and so forth). When you think about it, you will see that there are 24 possible permutations for the most general case (where [i,j,k,l] are all different). So by taking that into account, I assume it should at least be possible to limit the iteration range you took by calculating the output once and adding 24*sum for the general case. You will get different situations for [i,i,k,l] (12 cases for every i); [i,i,i,l] (in 4 cases for every i) and [i,i,i,i] (1 case for every i). You will need to account for that in your code.
When doing something like this, I would suggest you first leave out some dimensions, start to work with a 2 dimensional loop, first of all that will allow you to use this crude code and secondly that also allows you to study a simpler case first, find a faster solution and generalize that solution to your exact case.
For the 2D case, [i,j] represents a matrix and you will see that you can see that [i,j] and [j,i] gives the same output. However, a special case exists [i,i] only occurs once.
So for 2D, a naive implemtation might be something like:
   sum = 0;
   N=156;
   for i=1:N    
       for j=1:N    
          A = N - [i,j] + 1;
          sum = sum + min(A);
       end
   end
   sum
An implementation with fewer iterations (approximately half as many, if I'm right):
     sum = 0;
     N=156;
     for i=1:N    
       A = N - [i,i] + 1;
       sum = sum + min(A);
       for j=(i+1):N    
          A = N - [i,j] + 1;
          sum = sum + 2*min(A);
       end
     end
     sum
You can of course combine this with Robert Cumming's answer, precalculate the parts you already know.
Related Question